Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.09048 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908875588894720 |
|---|---|
| author | Bose, Prosenjit De Carufel, Jean-Lou Hill, Darryl Stuart, John |
| author_facet | Bose, Prosenjit De Carufel, Jean-Lou Hill, Darryl Stuart, John |
| contents | Given a finite set $P\subset\mathbb{R}^2$, the directed Theta-6 graph, denoted $\vecΘ_6(P)$, is a well-studied geometric graph due to its close relationship with the Delaunay triangulation. The $\vecΘ_6(P)$-graph is defined as follows: the plane around each point $u\in P$ is partitioned into $6$ equiangular cones with apex $u$, and in each cone, $u$ is joined to the point whose projection on the bisector of the cone is closest. Equivalently, the $\vecΘ_6(P)$-graph contains an edge from $u$ to $v$ exactly when the interior of $\nabla_u^v$ is disjoint from $P$, where $\nabla_u^v$ is the unique equilateral triangle containing $u$ on a corner, $v$ on the opposite side, and whose sides are parallel to the cone boundaries. It was previously shown that the spanning ratio of the $\vecΘ_6(P)$-graph is between $4$ and $7$ in the worst case (Akitaya, Biniaz, and Bose \emph{Comput. Geom.}, 105-106:101881, 2022). We close this gap by showing a tight spanning ratio of 5. This is the first tight bound proven for the spanning ratio of any $\vecΘ_k(P)$-graph. Our lower bound models a long path by mapping it to a converging series. Our upper bound proof uses techniques novel to the area of spanners. We use linear programming to prove that among several candidate paths, there exists a path satisfying our bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_09048 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Spanning Ratio of the Directed $Θ_6$-Graph is 5 Bose, Prosenjit De Carufel, Jean-Lou Hill, Darryl Stuart, John Computational Geometry 05C10 F.2.2; G.2.2 Given a finite set $P\subset\mathbb{R}^2$, the directed Theta-6 graph, denoted $\vecΘ_6(P)$, is a well-studied geometric graph due to its close relationship with the Delaunay triangulation. The $\vecΘ_6(P)$-graph is defined as follows: the plane around each point $u\in P$ is partitioned into $6$ equiangular cones with apex $u$, and in each cone, $u$ is joined to the point whose projection on the bisector of the cone is closest. Equivalently, the $\vecΘ_6(P)$-graph contains an edge from $u$ to $v$ exactly when the interior of $\nabla_u^v$ is disjoint from $P$, where $\nabla_u^v$ is the unique equilateral triangle containing $u$ on a corner, $v$ on the opposite side, and whose sides are parallel to the cone boundaries. It was previously shown that the spanning ratio of the $\vecΘ_6(P)$-graph is between $4$ and $7$ in the worst case (Akitaya, Biniaz, and Bose \emph{Comput. Geom.}, 105-106:101881, 2022). We close this gap by showing a tight spanning ratio of 5. This is the first tight bound proven for the spanning ratio of any $\vecΘ_k(P)$-graph. Our lower bound models a long path by mapping it to a converging series. Our upper bound proof uses techniques novel to the area of spanners. We use linear programming to prove that among several candidate paths, there exists a path satisfying our bound. |
| title | The Spanning Ratio of the Directed $Θ_6$-Graph is 5 |
| topic | Computational Geometry 05C10 F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2603.09048 |