Standard
The Tight Spanning Ratio of the Rectangle Delaunay Triangulation. / van Renssen, André; Sha, Yuan; Sun, Yucheng; Wong, Sampson.
31st Annual European Symposium on Algorithms, ESA 2023. ed. / Inge Li Gortz; Martin Farach-Colton; Simon J. Puglisi; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. p. 1-15 99 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 274).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
van Renssen, A, Sha, Y, Sun, Y
& Wong, S 2023,
The Tight Spanning Ratio of the Rectangle Delaunay Triangulation. in I Li Gortz, M Farach-Colton, SJ Puglisi & G Herman (eds),
31st Annual European Symposium on Algorithms, ESA 2023., 99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, LIPIcs, vol. 274, pp. 1-15, 31st Annual European Symposium on Algorithms, ESA 2023, Amsterdam, Netherlands,
04/09/2023.
https://doi.org/10.4230/LIPIcs.ESA.2023.99APA
van Renssen, A., Sha, Y., Sun, Y.
, & Wong, S. (2023).
The Tight Spanning Ratio of the Rectangle Delaunay Triangulation. In I. Li Gortz, M. Farach-Colton, S. J. Puglisi, & G. Herman (Eds.),
31st Annual European Symposium on Algorithms, ESA 2023 (pp. 1-15). [99] Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics, LIPIcs Vol. 274
https://doi.org/10.4230/LIPIcs.ESA.2023.99Vancouver
van Renssen A, Sha Y, Sun Y
, Wong S.
The Tight Spanning Ratio of the Rectangle Delaunay Triangulation. In Li Gortz I, Farach-Colton M, Puglisi SJ, Herman G, editors, 31st Annual European Symposium on Algorithms, ESA 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2023. p. 1-15. 99. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 274).
https://doi.org/10.4230/LIPIcs.ESA.2023.99Author
van Renssen, André ; Sha, Yuan ; Sun, Yucheng ; Wong, Sampson. / The Tight Spanning Ratio of the Rectangle Delaunay Triangulation. 31st Annual European Symposium on Algorithms, ESA 2023. editor / Inge Li Gortz ; Martin Farach-Colton ; Simon J. Puglisi ; Grzegorz Herman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. pp. 1-15 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 274).
Bibtex
@inproceedings{5332f32cd916412f93c5bd341ed93596,
title = "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 √2p1 + A2 + A√A2 + 1, which matches the known lower bound.",
keywords = "Delaunay Triangulation, Spanners, Spanning Ratio",
author = "{van Renssen}, Andr{\'e} and Yuan Sha and Yucheng Sun and Sampson Wong",
note = "Publisher Copyright: {\textcopyright} Andr{\'e} van Renssen, Yuan Sha, Yucheng Sun, and Sampson Wong;; 31st Annual European Symposium on Algorithms, ESA 2023 ; Conference date: 04-09-2023 Through 06-09-2023",
year = "2023",
doi = "10.4230/LIPIcs.ESA.2023.99",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
pages = "1--15",
editor = "{Li Gortz}, Inge and Martin Farach-Colton and Puglisi, {Simon J.} and Grzegorz Herman",
booktitle = "31st Annual European Symposium on Algorithms, ESA 2023",
}
RIS
TY - GEN
T1 - The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
AU - van Renssen, André
AU - Sha, Yuan
AU - Sun, Yucheng
AU - Wong, Sampson
N1 - Publisher Copyright:
© André van Renssen, Yuan Sha, Yucheng Sun, and Sampson Wong;
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - Delaunay Triangulation
KW - Spanners
KW - Spanning Ratio
U2 - 10.4230/LIPIcs.ESA.2023.99
DO - 10.4230/LIPIcs.ESA.2023.99
M3 - Article in proceedings
AN - SCOPUS:85173462748
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 15
BT - 31st Annual European Symposium on Algorithms, ESA 2023
A2 - Li Gortz, Inge
A2 - Farach-Colton, Martin
A2 - Puglisi, Simon J.
A2 - Herman, Grzegorz
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 31st Annual European Symposium on Algorithms, ESA 2023
Y2 - 4 September 2023 through 6 September 2023
ER -
