Elsevier

Journal of Algorithms

Volume 46, Issue 2, February 2003, Pages 178-189
Journal of Algorithms

Polynomial-time approximation schemes for packing and piercing fat objects

https://doi.org/10.1016/S0196-6774(02)00294-8Get rights and content

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.

References (30)

  • B.S Baker

    Approximation algorithms for NP-complete problems on planar graphs

    J. ACM

    (1994)
  • M de Berg et al.

    Realistic input models for geometric algorithms

  • P Berman et al.

    Improved approximation algorithms for rectangle tiling and packing

  • T.M Chan

    Approximate nearest neighbor queries revisited

    Discrete Comput. Geom.

    (1998)
  • T.H Cormen et al.

    Introduction to Algorithms

    (1990)
  • Cited by (0)

    1

    Work supported in part by an NSERC Research Grant.

    View full text