The Exact Spanning Ratio of the Parallelogram Delaunay Graph
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913247491260416 |
|---|---|
| author | Bose, Prosenjit De Carufel, Jean-Lou Njoo, Sandrine |
| author_facet | Bose, Prosenjit De Carufel, Jean-Lou Njoo, Sandrine |
| contents | Finding the exact spanning ratio of a Delaunay graph has been one of the longstanding open problems in Computational Geometry. Currently there are only four convex shapes for which the exact spanning ratio of their Delaunay graph is known: the equilateral triangle, the square, the regular hexagon and the rectangle. In this paper, we show the exact spanning ratio of the parallelogram Delaunay graph, making the parallelogram the fifth convex shape for which an exact bound is known. The worst-case spanning ratio is exactly $$\frac{\sqrt{2}\sqrt{1+A^2+2A\cos(θ_0)+(A+\cos(θ_0))\sqrt{1+A^2+2A\cos(θ_0)}}}{\sin(θ_0)} .$$ where $A$ is the aspect ratio and $θ_0$ is the non-obtuse angle of the parallelogram. Moreover, we show how to construct a parallelogram Delaunay graph whose spanning ratio matches the above mentioned spanning ratio. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_14305 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Exact Spanning Ratio of the Parallelogram Delaunay Graph Bose, Prosenjit De Carufel, Jean-Lou Njoo, Sandrine Computational Geometry Finding the exact spanning ratio of a Delaunay graph has been one of the longstanding open problems in Computational Geometry. Currently there are only four convex shapes for which the exact spanning ratio of their Delaunay graph is known: the equilateral triangle, the square, the regular hexagon and the rectangle. In this paper, we show the exact spanning ratio of the parallelogram Delaunay graph, making the parallelogram the fifth convex shape for which an exact bound is known. The worst-case spanning ratio is exactly $$\frac{\sqrt{2}\sqrt{1+A^2+2A\cos(θ_0)+(A+\cos(θ_0))\sqrt{1+A^2+2A\cos(θ_0)}}}{\sin(θ_0)} .$$ where $A$ is the aspect ratio and $θ_0$ is the non-obtuse angle of the parallelogram. Moreover, we show how to construct a parallelogram Delaunay graph whose spanning ratio matches the above mentioned spanning ratio. |
| title | The Exact Spanning Ratio of the Parallelogram Delaunay Graph |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2312.14305 |