The Tight Spanning Ratio of the Rectangle Delaunay Triangulation

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 790 KB, PDF-dokument

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.

OriginalsprogEngelsk
Titel31st Annual European Symposium on Algorithms, ESA 2023
RedaktørerInge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
ForlagSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publikationsdato2023
Sider1-15
Artikelnummer99
ISBN (Elektronisk)9783959772952
DOI
StatusUdgivet - 2023
Begivenhed31st Annual European Symposium on Algorithms, ESA 2023 - Amsterdam, Holland
Varighed: 4 sep. 20236 sep. 2023

Konference

Konference31st Annual European Symposium on Algorithms, ESA 2023
LandHolland
ByAmsterdam
Periode04/09/202306/09/2023
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind274
ISSN1868-8969

Bibliografisk note

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

ID: 382560215