Near-linear approximation algorithms for geometric hitting sets


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