Processing math: 100%

2506.12625

Total: 1

#1 Tight Routing and Spanning Ratios of Arbitrary Triangle Delaunay Graphs [PDF] [Copy] [Kimi] [REL]

Authors: Prosenjit Bose, Jean-Lou De Carufel, John Stuart

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 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θ2θ3. We prove that 1sin(θ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 TDθ1,θ2-Delaunay graphs with a routing ratio that is optimal in the worst case. When θ1=θ2=π3, our expressions for the spanning ratio and routing ratio evaluate to 2 and 53, matching the known tight bounds for TD-Delaunay graphs.

Subject: Computational Geometry

Publish: 2025-06-14 20:58:21 UTC