Skip to main navigation Skip to search Skip to main content

Covering and Partitioning Complex Objects with Small Pieces

  • Anders Aamand
  • , Mikkel Abrahamsen
  • , Reilly Browne
  • , Mayank Goswami
  • , Prahlad Narasimhan Kasthurirangan
  • , Linda Kleist
  • , Joseph S.B. Mitchell
  • , Valentin Polishchuk
  • , Jack Stade
  • University of Copenhagen
  • Dartmouth College
  • City University of New York
  • Stony Brook University
  • University of Hamburg
  • Linköping University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication42nd International Symposium on Computational Geometry, SoCG 2026
EditorsHee-Kap Ahn, Michael Hoffmann, Amir Nayyeri
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959774185
DOIs
StatePublished - May 27 2026
Event42nd International Symposium on Computational Geometry, SoCG 2026 - New Brunswick, United States
Duration: Jun 2 2026 → Jun 5 2026

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume367
ISSN (Print)1868-8969

Conference

Conference42nd International Symposium on Computational Geometry, SoCG 2026
Country/TerritoryUnited States
CityNew Brunswick
Period06/2/26 → 06/5/26

Keywords

  • Covering
  • partitioning
  • polygon
  • PTAS
  • small piece

Fingerprint

Dive into the research topics of 'Covering and Partitioning Complex Objects with Small Pieces'. Together they form a unique fingerprint.

Cite this