Covering the Boundary of a Simple Polygon with Geodesic Unit Disks

2014/07/02 by George Rabanca, Rabanca, George, Ivo Vigan +1
Computer Science · Engineering · #3D Shape Modeling and Analysis #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1407.0614

openalex publication_date 2014/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of covering the boundary of a simple polygon on n vertices using the minimum number of geodesic unit disks. We present an O(n log² n+k) time 2-approximation algorithm for finding the centers of the disks, with k denoting the number centers found by the algorithm.

Citations

• Minimum cell connection and separation in line segment arrangements
• Packing and Covering a Polygon with Geodesic Disks

Related

• Packing and Covering a Polygon with Geodesic Disks
• Computing the Geodesic Centers of a Polygonal Domain
• A linear-time algorithm for the geodesic center of a simple polygon
• Approximating the Smallest k-Enclosing Geodesic Disc in a Simple Polygon
• Approximating the Smallest k-Enclosing Geodesic Disc in a Simple Polygon