Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F19%3A00507671" target="_blank" >RIV/67985807:_____/19:00507671 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21240/19:00332438

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-030-24766-9_15" target="_blank" >http://dx.doi.org/10.1007/978-3-030-24766-9_15</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-24766-9_15" target="_blank" >10.1007/978-3-030-24766-9_15</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs

Popis výsledku v původním jazyce

We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape C . Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k- DGC(S) , has vertex set S and edge pq provided that there exists some homothet of C with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graph k- GGC(S) is defined analogously, except for the fact that the homothets considered are restricted to be smallest homothets of C with p and q on its boundary. We provide upper bounds on the minimum value of k for which k- GGC(S) is Hamiltonian. Since k- GGC(S) ⊆ k- DGC(S) , all results carry over to k- DGC(S) . In particular, we give upper bounds of 24 for every C and 15 for every point-symmetric C . We also improve the bound to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for t≥10) . These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs.

Název v anglickém jazyce

Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs

Popis výsledku anglicky

We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape C . Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k- DGC(S) , has vertex set S and edge pq provided that there exists some homothet of C with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graph k- GGC(S) is defined analogously, except for the fact that the homothets considered are restricted to be smallest homothets of C with p and q on its boundary. We provide upper bounds on the minimum value of k for which k- GGC(S) is Hamiltonian. Since k- GGC(S) ⊆ k- DGC(S) , all results carry over to k- DGC(S) . In particular, we give upper bounds of 24 for every C and 15 for every point-symmetric C . We also improve the bound to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for t≥10) . These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GJ19-06792Y" target="_blank" >GJ19-06792Y: Strukturální vlastnosti viditelnosti terénů a Voroného diagramů nejvzdálenější barvy</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

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ů

Název statě ve sborníku

Algorithms and Data Structures

ISBN

978-3-030-24765-2

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

15

Strana od-do

196-210

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Edmonton

Datum konání akce

5. 8. 2019

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000716936200015