Approximating the piercing number for unit-height rectangles

Timothy M. Chan, Abdullah Al Mahmood

Research output: Contribution to conferencePaperpeer-review

Abstract

The piercing problem seeks the minimum number of points for a set of objects such that each object contains at least one of the points. We present a polynomial-time approximation scheme (PTAS) for the piercing problem for a set of axis-parallel unit-height rectangles. We also examine the problem in a dynamic setting and show how to maintain a factor-2 approximation under insertions in logarithmic amortized time, by solving an incremental version of the maximum independent set problem for interval graphs.

Original languageEnglish (US)
Pages15-18
Number of pages4
StatePublished - Jan 1 2005
Externally publishedYes
Event17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, Canada
Duration: Aug 10 2005Aug 12 2005

Conference

Conference17th Canadian Conference on Computational Geometry, CCCG 2005
CountryCanada
CityWindsor
Period8/10/058/12/05

ASJC Scopus subject areas

  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Approximating the piercing number for unit-height rectangles'. Together they form a unique fingerprint.

Cite this