{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreia44axg4cdghfkmtavb6vlxifmggwzlopvkh2iiuovu4s6txzv2aq",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhu7qdmtoo32"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.23216v1",
  "publishedAt": "2026-03-25T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Anders Aamand",
    "Mikkel Abrahamsen",
    "Reilly Browne",
    "Mayank Goswami",
    "Prahlad Narasimhan Kasthurirangan",
    "Linda Kleist",
    "Joseph S. B. Mitchell",
    "Valentin Polishchuk",
    "Jack Stade"
  ],
  "textContent": "**Authors:** Anders Aamand, Mikkel Abrahamsen, Reilly Browne, Mayank Goswami, Prahlad Narasimhan Kasthurirangan, Linda Kleist, Joseph S. B. Mitchell, Valentin Polishchuk, Jack Stade\n\nWe 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"
}