The Tight Spanning Ratio of the Rectangle Delaunay Triangulation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909546095575040 |
|---|---|
| author | van Renssen, Andrè Sha, Yuan Sun, Yucheng Wong, Sampson |
| author_facet | van Renssen, Andrè Sha, Yuan Sun, Yucheng Wong, Sampson |
| contents | 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 $\sqrt{2} \sqrt{1+A^2 + A \sqrt{A^2 + 1}}$, which matches the known lower bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_11987 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The Tight Spanning Ratio of the Rectangle Delaunay Triangulation van Renssen, Andrè Sha, Yuan Sun, Yucheng Wong, Sampson Computational Geometry F.2.2 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 $\sqrt{2} \sqrt{1+A^2 + A \sqrt{A^2 + 1}}$, which matches the known lower bound. |
| title | The Tight Spanning Ratio of the Rectangle Delaunay Triangulation |
| topic | Computational Geometry F.2.2 |
| url | https://arxiv.org/abs/2211.11987 |