Approximating the piercing number for unit-height rectangles

Timothy M. Chan; Abdullah Al Mahmood

Approximating the piercing number for unit-height rectangles

Research output: Contribution to conference › Paper › peer-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 language	English (US)
Pages	15-18
Number of pages	4
State	Published - 2005
Externally published	Yes
Event	17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, Canada Duration: Aug 10 2005 → Aug 12 2005

Conference

Conference	17th Canadian Conference on Computational Geometry, CCCG 2005
Country/Territory	Canada
City	Windsor
Period	8/10/05 → 8/12/05

ASJC Scopus subject areas

Geometry and Topology
Computational Mathematics

Library availability

Discover UIUC Full Text

Cite this

@conference{92545a1ceb4b4d6aa142b2dffb3c90aa,

title = "Approximating the piercing number for unit-height rectangles",

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.",

author = "Chan, {Timothy M.} and Mahmood, {Abdullah Al}",

year = "2005",

language = "English (US)",

pages = "15--18",

note = "17th Canadian Conference on Computational Geometry, CCCG 2005 ; Conference date: 10-08-2005 Through 12-08-2005",

}

TY - CONF

T1 - Approximating the piercing number for unit-height rectangles

AU - Chan, Timothy M.

AU - Mahmood, Abdullah Al

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84863404066&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863404066&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:84863404066

SP - 15

EP - 18

T2 - 17th Canadian Conference on Computational Geometry, CCCG 2005

Y2 - 10 August 2005 through 12 August 2005

ER -

Approximating the piercing number for unit-height rectangles

Abstract

Conference

ASJC Scopus subject areas

Library availability

Related links

Fingerprint

Cite this