2026-09-05T11:58:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25826 2026-06-23T12:59:06Z ddc:004 open_access

The Spanning Ratio of the Directed Θ₆-Graph Is 5 Bose, Prosenjit De Carufel, Jean-Lou Stuart, John Hill, Darryl Geometric Spanners Theta Graphs Directed Theta Graphs Spanning Ratio Computational Geometry Given a finite set P ⊂ ℝ², the directed Theta-6 graph, denoted Θ₆(P), is a well-studied geometric graph due to its close relationship with the Delaunay triangulation. The Θ₆(P)-graph is defined as follows: the plane around each point u ∈ 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 Θ₆(P)-graph contains an edge from u to v exactly when the interior of ∇_u^v is disjoint from P, where ∇_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 Θ₆(P)-graph is between 4 and 7 in the worst case (Akitaya, Biniaz, and Bose 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 Θ_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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prosenjit Bose and Jean-Lou De Carufel and John Stuart and Darryl Hill 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.20 urn:nbn:de:0030-drops-258268 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.20 eng https://creativecommons.org/licenses/by/4.0/legalcode