2025/06/14 by Prosenjit Bose, Bose, Prosenjit, Jean-Lou De Carufel +2
Computer Science · Engineering · #3D Modeling in Geospatial Applications #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2506.12625
openalex publication_date 2025/06/14 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28
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 (1)/(sin(θ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=\fracπ3, our expressions for the spanning ratio and routing ratio evaluate to 2 and (√(5))/(3), matching the known tight bounds for TD-Delaunay graphs.