Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs
The result's identifiers
Result code in 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>
Alternative codes found
RIV/68407700:21240/19:00332438
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GJ19-06792Y" target="_blank" >GJ19-06792Y: Structural properties of visibility in terrains and farthest color Voronoi diagrams</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2019
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
Algorithms and Data Structures
ISBN
978-3-030-24765-2
ISSN
0302-9743
e-ISSN
—
Number of pages
15
Pages from-to
196-210
Publisher name
Springer
Place of publication
Cham
Event location
Edmonton
Event date
Aug 5, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000716936200015