Near-linear approximation algorithms for geometric hitting sets
Published
Journal Article
Given a range space (X,R), where R § 2 X, the hitting set problem is to find a smallest-cardinality subset H § X that intersects each set in R. We present near-linear-time approximation algorithms for the hitting set problem in the following geometric settings: (i) R is a set of planar regions with small union complexity. (ii) R is a set of axis-parallel d-dimensional boxes in Rd . In both cases X is either the entire R d , or a finite set of points in R d . The approximation factors yielded by the algorithm are small; they are either the same as, or within very small factors off the best factors known to be computable in polynomial time. © Springer Science+Business Media, LLC 2011.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Ezra, E; Sharir, M
Published Date
- June 1, 2012
Published In
Volume / Issue
- 63 / 1-2
Start / End Page
- 1 - 25
Electronic International Standard Serial Number (EISSN)
- 1432-0541
International Standard Serial Number (ISSN)
- 0178-4617
Digital Object Identifier (DOI)
- 10.1007/s00453-011-9517-2
Citation Source
- Scopus