Covering and Partitioning Complex Objects with Small Pieces
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918406652952576 |
|---|---|
| author | Aamand, Anders Abrahamsen, Mikkel Browne, Reilly Goswami, Mayank Kasthurirangan, Prahlad Narasimhan Kleist, Linda Mitchell, Joseph S. B. Polishchuk, Valentin Stade, Jack |
| author_facet | Aamand, Anders Abrahamsen, Mikkel Browne, Reilly Goswami, Mayank Kasthurirangan, Prahlad Narasimhan Kleist, Linda Mitchell, Joseph S. B. Polishchuk, Valentin Stade, Jack |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_23216 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Covering and Partitioning Complex Objects with Small Pieces Aamand, Anders Abrahamsen, Mikkel Browne, Reilly Goswami, Mayank Kasthurirangan, Prahlad Narasimhan Kleist, Linda Mitchell, Joseph S. B. Polishchuk, Valentin Stade, Jack Computational Geometry 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. |
| title | Covering and Partitioning Complex Objects with Small Pieces |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2603.23216 |