Decomposing a Simple Polygon with Geodesic Unit-Balls
2026-07-10 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study how to divide a simple polygon into pieces that either have a maximum geodesic radius or diameter of one, using standard distance measurements. Since exact solutions are not known and the problem is hard for polygons with holes, they focus on creating simpler algorithms that run efficiently. They provide the first approximation algorithms for covering and partitioning polygons by radius with a factor of 9. For partitioning by diameter, they improve previous complex methods by offering a simpler algorithm with a 15-approximation factor.
simple polygongeodesic radiusgeodesic diameterpolygon coveringpolygon partitioningapproximation algorithmpolynomial timeNP-hardℓ2-metric
Authors
Reilly Browne, Prahlad Narasimhan Kasthurirangan
Abstract
We consider covering and partitioning a simple polygon into pieces which either have unit geodesic radius or unit geodesic diameter, using the $\ell_2$-metric for distances. There is no known method for finding an exact solution to these problems, even when the input size is constant, and the problem is known to be NP-hard in the case of polygons with holes. With this in mind, we instead devote our attention to developing simple approximation algorithms that run in polynomial time. For the radius problem, we present the first known approximation algorithms for both covering and partitioning, achieving a factor of 9. For the diameter problem, we are only able to give a positive result for the partition version of the problem, where we improve upon a complicated 72-approximation from Abrahamsen and Rasmussen [SODA '25], achieving a simple 15-approximation.