The Tight Spanning Ratio of the Rectangle Delaunay Triangulation

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Final published version, 790 KB, PDF document

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 √2p1 + A2 + A√A2 + 1, which matches the known lower bound.

Original languageEnglish
Title of host publication31st Annual European Symposium on Algorithms, ESA 2023
EditorsInge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date2023
Pages1-15
Article number99
ISBN (Electronic)9783959772952
DOIs
Publication statusPublished - 2023
Event31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Netherlands
Duration: 4 Sep 20236 Sep 2023

Conference

Conference31st Annual European Symposium on Algorithms, ESA 2023
LandNetherlands
ByAmsterdam
Periode04/09/202306/09/2023
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume274
ISSN1868-8969

Bibliographical note

Publisher Copyright:
© André van Renssen, Yuan Sha, Yucheng Sun, and Sampson Wong;

    Research areas

  • Delaunay Triangulation, Spanners, Spanning Ratio

ID: 382560215