License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.99
URN: urn:nbn:de:0030-drops-187523
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18752/
van Renssen, André ;
Sha, Yuan ;
Sun, Yucheng ;
Wong, Sampson
The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
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.
BibTeX - Entry
@InProceedings{vanrenssen_et_al:LIPIcs.ESA.2023.99,
author = {van Renssen, Andr\'{e} and Sha, Yuan and Sun, Yucheng and Wong, Sampson},
title = {{The Tight Spanning Ratio of the Rectangle Delaunay Triangulation}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {99:1--99:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18752},
URN = {urn:nbn:de:0030-drops-187523},
doi = {10.4230/LIPIcs.ESA.2023.99},
annote = {Keywords: Spanners, Delaunay Triangulation, Spanning Ratio}
}
|
Keywords: |
|
Spanners, Delaunay Triangulation, Spanning Ratio |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
