Document Open Access Logo

The Tight Spanning Ratio of the Rectangle Delaunay Triangulation

Authors André van Renssen , Yuan Sha, Yucheng Sun, Sampson Wong

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.99.pdf
  • Filesize: 0.77 MB
  • 15 pages

Document Identifiers

Author Details

André van Renssen
  • University of Sydney, Australia
Yuan Sha
  • University of Sydney, Australia
Yucheng Sun
  • University of Sydney, Australia
Sampson Wong
  • BARC, University of Copenhagen, Denmark

Cite AsGet BibTex

André van Renssen, Yuan Sha, Yucheng Sun, and Sampson Wong. The Tight Spanning Ratio of the Rectangle Delaunay Triangulation. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 99:1-99:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.99

Abstract

Spanner construction is a well-studied problem and Delaunay triangulations are among the most popular spanners. Tight bounds are known if the Delaunay triangulation is constructed using an equilateral triangle, a square, or a regular hexagon. However, all other shapes have remained elusive. In this paper we extend the restricted class of spanners for which tight bounds are known. We prove that Delaunay triangulations constructed using rectangles with aspect ratio A have spanning ratio at most √2 √{1+A² + A √{A²+1}}, which matches the known lower bound.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Spanners
  • Delaunay Triangulation
  • Spanning Ratio

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, and Ljubomir Perković. Tight stretch factors for L₁- and L_∞-Delaunay triangulations. Computational Geometry: Theory and Applications (CGTA), 48(3):237-250, 2015. Google Scholar
  2. Prosenjit Bose, Paz Carmi, Sébastien Collette, and Michiel Smid. On the stretch factor of convex Delaunay graphs. Journal of Computational Geometry (JoCG), 1(1):41-56, 2010. Google Scholar
  3. Prosenjit Bose, Jean-Lou De Carufel, and André van Renssen. Constrained generalized Delaunay graphs are plane spanners. Computational Geometry: Theory and Applications (CGTA), 74:50-65, 2018. Google Scholar
  4. Prosenjit Bose, Luc Devroye, Maarten Löffler, Jack Snoeyink, and Vishal Verma. Almost all Delaunay triangulations have stretch factor greater than π/2. Computational Geometry: Theory and Applications (CGTA), 44(2):121-127, 2011. Google Scholar
  5. Prosenjit Bose and Michiel Smid. On plane geometric spanners: A survey and open problems. Computational Geometry: Theory and Applications (CGTA), 46(7):818-830, 2013. Google Scholar
  6. L. Paul Chew. There is a planar graph almost as good as the complete graph. In Proceedings of the 2nd Annual Symposium on Computational Geometry (SoCG), pages 169-177, 1986. Google Scholar
  7. L. Paul Chew. There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences (JCSS), 39(2):205-219, 1989. Google Scholar
  8. David P. Dobkin, Steven J. Friedman, and Kenneth J. Supowit. Delaunay graphs are almost as good as complete graphs. Discrete & Computational Geometry (DCG), 5(1):399-407, 1990. Google Scholar
  9. J. Mark Keil and Carl A. Gutwin. Classes of graphs which approximate the complete Euclidean graph. Discrete & Computational Geometry (DCG), 7(1):13-28, 1992. Google Scholar
  10. Der-Tsai Lee and Arthur K. Lin. Generalized Delaunay triangulation for planar graphs. Discrete & Computational Geometry (DCG), 1(3):201-217, 1986. Google Scholar
  11. Giri Narasimhan and Michiel Smid. Geometric Spanner Networks. Cambridge University Press, 2007. Google Scholar
  12. Ljubomir Perković, Michael Dennis, and Duru Türkoğlu. The stretch factor of hexagon-Delaunay triangulations. Journal of Computational Geometry (JoCG), 12(2):86-125, 2021. Google Scholar
  13. André van Renssen, Yuan Sha, Yucheng Sun, and Sampson Wong. The tight spanning ratio of the rectangle Delaunay triangulation, 2022. URL: https://arxiv.org/abs/2211.11987.
  14. Ge Xia. The stretch factor of the Delaunay triangulation is less than 1.998. SIAM Journal on Computing (SICOMP), 42(4):1620-1659, 2013. Google Scholar
  15. Ge Xia and Liang Zhang. Toward the tight bound of the stretch factor of Delaunay triangulations. In Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG 2011), pages 175-180, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact