2020/09/15 by André van Renssen, van Renssen, André, Gladys Wong +1
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Robotic Path Planning Algorithms #Smart Parking Systems Research
paper · pdf · doi:10.48550/arxiv.2009.06879
openalex publication_date 2020/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let V be a finite set of vertices in the plane and S be a finite set of polygonal obstacles, where the vertices of S are in V. We show how to construct a plane 2-spanner of the visibility graph of V with respect to S. As this graph can have unbounded degree, we modify it in three easy-to-follow steps, in order to bound the degree to 7 at the cost of slightly increasing the spanning ratio to 6.