Near-linear approximation algorithms for geometric hitting sets
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.
Agarwal, PK; Ezra, E; Sharir, M
Volume / Issue
Start / End Page
Electronic International Standard Serial Number (EISSN)
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)