2026-07-22T13:37:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18752 2024-03-06T11:02:38Z ddc:004 open_access

The Tight Spanning Ratio of the Rectangle Delaunay Triangulation van Renssen, André Sha, Yuan Sun, Yucheng Wong, Sampson Spanners Delaunay Triangulation Spanning Ratio 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik André van Renssen and Yuan Sha and Yucheng Sun and Sampson Wong 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.99 urn:nbn:de:0030-drops-187523 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.99 eng https://creativecommons.org/licenses/by/4.0/legalcode