## 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