On planar point sets with the pentagon property
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10144027" target="_blank" >RIV/00216208:11320/13:10144027 - isvavai.cz</a>
Result on the web
<a href="http://dl.acm.org/citation.cfm?id=2462406" target="_blank" >http://dl.acm.org/citation.cfm?id=2462406</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/2462356.2462406" target="_blank" >10.1145/2462356.2462406</a>
Alternative languages
Result language
angličtina
Original language name
On planar point sets with the pentagon property
Original language description
Motivated by recent papers of Eppstein, Abel et al. and Barat et al., and by a question of Wood, we investigate properties of planar point sets with no 5-hole (no empty convex pentagon). We answer a question of Wood by showing that the visibility graph of a finite point set with no 5-hole may contain a clique of arbitrary size. This is in contrast with the previous examples of sets with no 5-hole, including the example of the (finite) square lattice. In our construction we use several equivalent local characterizations of (locally) finite planar point sets with no 5-hole which may be of independent interest. Our construction relies on a construction scheme which allows to derive new, non-trivial examples of sets with no 5-hole.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the twenty-ninth annual symposium on Computational geometry
ISBN
978-1-4503-2031-3
ISSN
—
e-ISSN
—
Number of pages
10
Pages from-to
81-90
Publisher name
Association for Computing Machinery
Place of publication
New York, USA
Event location
Rio de Janeiro, Brazílie
Event date
Jun 17, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—