Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs

Autoři: Maria Saumell
Rok vydání: 2019
Typ publikace: Konferenční příspěvek (mezinárodní konf.)
Periodikum: Algorithms and Data Structures
Projekty: Strukturální vlastnosti viditelnosti terénů a Voroného diagramů nejvzdálenější barvy
Bibliografická citace: BOSE, P., CANO, P., SAUMELL, Maria, SILVEIRA, R. Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs. In: FRIGGSTAD, Z., SACK, J.-R., SALAVATIPOUR, M., eds. Algorithms and Data Structures. Cham: Springer, 2019, S. 196-210. Lecture Notes in Computer Science, 11646. ISBN 978-3-030-24765-2. ISSN 0302-9743
Dostupné z: doi:10.1007/978-3-030-24766-9_15
DOI: 10.1007/978-3-030-24766-9_15
ID: 507671

Abstrakt

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.