2007/02/20 by Prosenjit Bose, Bose, Prosenjit, Paz Carmi +7 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #Robotic Path Planning Algorithms #cs.CG
paper · pdf · doi:10.48550/arxiv.cs/0702117
openalex publication_date 2007/02/20 · arxiv created 2007/02/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a family of directed geometric graphs, denoted \paz, that depend on two parameters λ and θ. For 0≤ θ<\fracπ2 and 1/2 < λ< 1, the \paz graph is a strong t-spanner, with t=(1)/((1-λ)cosθ). The out-degree of a node in the \paz graph is at most \lfloor2π/min(θ, \arccos(1)/(2λ))\rfloor. Moreover, we show that routing can be achieved locally on \paz. Next, we show that all strong t-spanners are also t-spanners of the unit disk graph. Simulations for various values of the parameters λ and θ indicate that for random point sets, the spanning ratio of \paz is better than the proven theoretical bounds.