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 language | English (US) |
---|---|
Pages (from-to) | 178-189 |
Number of pages | 12 |
Journal | Journal of Algorithms |
Volume | 46 |
Issue number | 2 |
DOIs | |
State | Published - Feb 2003 |
Externally published | Yes |
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