LIPIcs.SoCG.2020.34.pdf
- Filesize: 0.58 MB
- 16 pages
Document
The Stretch Factor of Hexagon-Delaunay Triangulations
Authors
-
Part of:
Volume:
36th International Symposium on Computational Geometry (SoCG 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-08
Cite As Get BibTex
Michael Dennis, Ljubomir Perković, and Duru Türkoğlu. The Stretch Factor of Hexagon-Delaunay Triangulations. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.34
Abstract
The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch factor) of a Delaunay triangulation is one of the longstanding open problems in computational geometry. Over the years, a series of upper and lower bounds on the exact stretch factor have been obtained but the gap between them is still large. An alternative approach to solving the problem is to develop techniques for computing the exact stretch factor of "easier" types of Delaunay triangulations, in particular those defined using regular-polygons instead of a circle. Tight bounds exist for Delaunay triangulations defined using an equilateral triangle and a square. In this paper, we determine the exact stretch factor of Delaunay triangulations defined using a regular hexagon: It is 2. We think that the main contribution of this paper are the two techniques we have developed to compute tight upper bounds for the stretch factor of Hexagon-Delaunay triangulations.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
- Theory of computation → Sparsification and spanners
- Theory of computation → Shortest paths
Keywords
- Delaunay triangulation
- geometric spanner
- plane spanner
- stretch factor
- spanning ratio
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Nicolas Bonichon, 2011. Personal communication.
-
Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perković. Tight stretch factors for L₁- and L_∞-Delaunay triangulations. Computational Geometry, 48(3):237-250, 2015.
-
Prosenjit Bose, Paz Carmi, Sebastien Collette, and Michiel Smid. On the stretch factor of convex Delaunay graphs. Journal of Computational Geometry, 1(1):41-56, 2010.
-
Prosenjit Bose, Luc Devroye, Maarten Löffler, Jack Snoeyink, and Vishal Verma. Almost all Delaunay triangulations have stretch factor greater than π/2. Computational Geometry, 44(2):121-127, 2011.
-
L. Paul Chew. There is a planar graph almost as good as the complete graph. In Proceedings of the 2nd Annual ACM Symposium on Computational Geometry (SoCG), pages 169-177, 1986.
-
L. Paul Chew. There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences, 39(2):205-219, 1989.
- Michael Dennis, Ljubomir Perković, and Duru Türkoğlu. The stretch factor of hexagon-delaunay triangulations, 2017. URL: http://arxiv.org/abs/1711.00068.
-
David P. Dobkin, Steven J. Friedman, and Kenneth J. Supowit. Delaunay graphs are almost as good as complete graphs. Discrete & Computational Geometry, 5(4):399-407, 1990.
-
J. Mark Keil and Carl A. Gutwin. Classes of graphs which approximate the complete Euclidean graph. Discrete & Computational Geometry, 7(1):13-28, 1992.
- Ge Xia. The stretch factor of the Delaunay triangulation is less than 1.998. SIAM Journal on Computing, 42(4):1620-1659, 2013. URL: https://doi.org/10.1137/110832458.
- Ge Xia and Liang Zhang. Toward the tight bound of the stretch factor of Delaunay triangulations. In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG), 2011. URL: http://www.cccg.ca/proceedings/2011/papers/paper57.pdf.