2026-09-30T02:35:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25807 2026-09-23T23:51:05Z ddc:004 open_access

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 Covering partitioning polygon small piece PTAS 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anders Aamand and Mikkel Abrahamsen and Reilly Browne and Mayank Goswami and Prahlad Narasimhan Kasthurirangan and Linda Kleist and Joseph S. B. Mitchell and Valentin Polishchuk and Jack Stade 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.1 urn:nbn:de:0030-drops-258077 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.1 eng https://creativecommons.org/licenses/by/4.0/legalcode