Tight Routing and Spanning Ratios of Arbitrary Triangle Delaunay Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908408039342080 |
|---|---|
| author | Bose, Prosenjit De Carufel, Jean-Lou Stuart, John |
| author_facet | Bose, Prosenjit De Carufel, Jean-Lou Stuart, John |
| contents | A Delaunay graph built on a planar point set has an edge between two vertices when there exists a disk with the two vertices on its boundary and no vertices in its interior. When the disk is replaced with an equilateral triangle, the resulting graph is known as a Triangle-Distance Delaunay Graph or TD-Delaunay for short. A generalized $\text{TD}_{θ_1,θ_2}$-Delaunay graph is a TD-Delaunay graph whose empty region is a scaled translate of a triangle with angles of $θ_1,θ_2,θ_3:=π-θ_1-θ_2$ with $θ_1\leqθ_2\leqθ_3$. We prove that $\frac{1}{\sin(θ_1/2)}$ is a lower bound on the spanning ratio of these graphs which matches the best known upper bound (Lubiw & Mondal, J. Graph Algorithms Appl., 23(2):345-369). Then we provide an online local routing algorithm for $\text{TD}_{θ_1,θ_2}$-Delaunay graphs with a routing ratio that is optimal in the worst case. When $θ_1=θ_2=\fracπ{3}$, our expressions for the spanning ratio and routing ratio evaluate to $2$ and $\frac{\sqrt{5}}{3}$, matching the known tight bounds for TD-Delaunay graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12625 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Routing and Spanning Ratios of Arbitrary Triangle Delaunay Graphs Bose, Prosenjit De Carufel, Jean-Lou Stuart, John Computational Geometry A Delaunay graph built on a planar point set has an edge between two vertices when there exists a disk with the two vertices on its boundary and no vertices in its interior. When the disk is replaced with an equilateral triangle, the resulting graph is known as a Triangle-Distance Delaunay Graph or TD-Delaunay for short. A generalized $\text{TD}_{θ_1,θ_2}$-Delaunay graph is a TD-Delaunay graph whose empty region is a scaled translate of a triangle with angles of $θ_1,θ_2,θ_3:=π-θ_1-θ_2$ with $θ_1\leqθ_2\leqθ_3$. We prove that $\frac{1}{\sin(θ_1/2)}$ is a lower bound on the spanning ratio of these graphs which matches the best known upper bound (Lubiw & Mondal, J. Graph Algorithms Appl., 23(2):345-369). Then we provide an online local routing algorithm for $\text{TD}_{θ_1,θ_2}$-Delaunay graphs with a routing ratio that is optimal in the worst case. When $θ_1=θ_2=\fracπ{3}$, our expressions for the spanning ratio and routing ratio evaluate to $2$ and $\frac{\sqrt{5}}{3}$, matching the known tight bounds for TD-Delaunay graphs. |
| title | Tight Routing and Spanning Ratios of Arbitrary Triangle Delaunay Graphs |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2506.12625 |