The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language | English |
---|---|
Title of host publication | 31st Annual European Symposium on Algorithms, ESA 2023 |
Editors | Inge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Publication date | 2023 |
Pages | 1-15 |
Article number | 99 |
ISBN (Electronic) | 9783959772952 |
DOIs | |
Publication status | Published - 2023 |
Event | 31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Netherlands Duration: 4 Sep 2023 → 6 Sep 2023 |
Conference
Conference | 31st Annual European Symposium on Algorithms, ESA 2023 |
---|---|
Land | Netherlands |
By | Amsterdam |
Periode | 04/09/2023 → 06/09/2023 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 274 |
ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:
© André van Renssen, Yuan Sha, Yucheng Sun, and Sampson Wong;
- Delaunay Triangulation, Spanners, Spanning Ratio
Research areas
ID: 382560215