Total: 1
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.