Tight Routing and Spanning Ratios of Arbitrary Triangle Delaunay Graphs

Abstract

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}}_{{\theta }_1,{\theta }_2}$-Delaunay graph is a TD-Delaunay graph whose empty region is a scaled translate of a triangle with angles of ${\theta }_1,{\theta }_2,{\theta }_3:=\pi -{\theta }_1-{\theta }_2$ with ${\theta }_1\le {\theta }_2\le {\theta }_3$. We prove that $\frac{1}{\sin ({\theta }_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}}_{{\theta }_1,{\theta }_2}$-Delaunay graphs with a routing ratio that is optimal in the worst case. When ${\theta }_1={\theta }_2=\frac{\pi }{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.