On planar point sets with the pentagon property
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On planar point sets with the pentagon property
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
On planar point sets with the pentagon property
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2013
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings of the twenty-ninth annual symposium on Computational geometry
ISBN
978-1-4503-2031-3
ISSN
—
e-ISSN
—
Počet stran výsledku
10
Strana od-do
81-90
Název nakladatele
Association for Computing Machinery
Místo vydání
New York, USA
Místo konání akce
Rio de Janeiro, Brazílie
Datum konání akce
17. 6. 2013
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—