Covering and Partitioning Complex Objects with Small Pieces
This addresses computational geometry problems for efficient shape decomposition, with foundational algorithmic advances in 2D and hardness results in 3D.
The paper tackles the problem of covering or partitioning polygons (with holes) using the minimum number of small pieces contained in unit squares, showing that optimal covers and partitions have the same number of pieces. It provides the first PTAS for 2D polygons with a 1+O(1/√k)-approximation via local search, while proving NP-hardness for 3D polyhedra with logarithmic inapproximability.
We study the problems of covering or partitioning a polygon $P$ (possibly with holes) using a minimum number of small pieces, where a small piece is a connected sub-polygon contained in an axis-aligned unit square. For covering, we seek to write $P$ as a union of small pieces, and in partitioning, we furthermore require the pieces to be pairwise interior-disjoint. We show that these problems are in fact equivalent: Optimum covers and partitions have the same number of pieces. For covering, a natural local search algorithm repeatedly attempts to replace $k$ pieces from a candidate cover with $k-1$ pieces. In two dimensions and for sufficiently large $k$, we show that when no such swap is possible, the cover is a $1+O(1/\sqrt k)$-approximation, hence obtaining the first PTAS for the problem. Prior to our work, the only known algorithm was a $13$-approximation that only works for polygons without holes [Abrahamsen and Rasmussen, SODA 2025]. In contrast, in the three dimensional version of the problem, for a polyhedron $P$ of complexity $n$, we show that it is NP-hard to approximate an optimal cover or partition to within a factor that is logarithmic in $n$, even if $P$ is simple, i.e., has genus $0$ and no holes.