Polynomial-time approximation schemes for packing and piercing fat objects

Research output: Contribution to journalArticlepeer-review

Abstract

We consider two problems: given a collection of n fat objects in a fixed dimension, (1) (packing) find the maximum subcollection of pairwise disjoint objects, and (2) (piercing) find the minimum point set that intersects every object. Recently, Erlebach, Jansen, and Seidel gave a polynomial-time approximation scheme (PTAS) for the packing problem, based on a shifted hierarchical subdivision method. Using shifted quadtrees, we describe a similar algorithm for packing but with a smaller time bound. Erlebach et al.'s algorithm requires polynomial space. We describe a different algorithm, based on geometric separators, that requires only linear space. This algorithm can also be applied to piercing, yielding the first PTAS for that problem.

Original languageEnglish (US)
Pages (from-to)178-189
Number of pages12
JournalJournal of Algorithms
Volume46
Issue number2
DOIs
StatePublished - Feb 2003
Externally publishedYes

Keywords

  • Approximation algorithms
  • Computational geometry
  • Dynamic programming
  • Hitting set
  • Maximum independent set
  • Quadtrees
  • Separator theorems

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Polynomial-time approximation schemes for packing and piercing fat objects'. Together they form a unique fingerprint.

Cite this