TY - GEN
T1 - Covering and Partitioning Complex Objects with Small Pieces
AU - Aamand, Anders
AU - Abrahamsen, Mikkel
AU - Browne, Reilly
AU - Goswami, Mayank
AU - Kasthurirangan, Prahlad Narasimhan
AU - Kleist, Linda
AU - Mitchell, Joseph S.B.
AU - Polishchuk, Valentin
AU - Stade, Jack
N1 - Publisher Copyright:
© Anders Aamand, Mikkel Abrahamsen, Reilly Browne, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph S. B. Mitchell, Valentin Polishchuk, and Jack Stade;
PY - 2026/5/27
Y1 - 2026/5/27
N2 - 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/√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.
AB - 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/√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.
KW - Covering
KW - partitioning
KW - polygon
KW - PTAS
KW - small piece
UR - https://www.scopus.com/pages/publications/105041222200
U2 - 10.4230/LIPIcs.SoCG.2026.1
DO - 10.4230/LIPIcs.SoCG.2026.1
M3 - Conference contribution
AN - SCOPUS:105041222200
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 42nd International Symposium on Computational Geometry, SoCG 2026
A2 - Ahn, Hee-Kap
A2 - Hoffmann, Michael
A2 - Nayyeri, Amir
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 42nd International Symposium on Computational Geometry, SoCG 2026
Y2 - 2 June 2026 through 5 June 2026
ER -