Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

Published

Journal Article

© 2019, Springer Science+Business Media, LLC, part of Springer Nature. Given a finite range space Σ = (X, R) , with N= | X| + | R| , we present two simple algorithms, based on the multiplicative-weight method, for computing a small-size hitting set or set cover of Σ. The first algorithm is a simpler variant of the Brönnimann–Goodrich algorithm but more efficient to implement, and the second algorithm can be viewed as solving a two-player zero-sum game. These algorithms, in conjunction with some standard geometric data structures, lead to near-linear algorithms for computing a small-size hitting set or set cover for a number of geometric range spaces. For example, they lead to O(Npolylog (N)) expected-time randomized O(1)-approximation algorithms for both hitting set and set cover if X is a set of points and R a set of disks in R 2 .

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Pan, J

Published Date

  • January 1, 2019

Published In

Electronic International Standard Serial Number (EISSN)

  • 1432-0444

International Standard Serial Number (ISSN)

  • 0179-5376

Digital Object Identifier (DOI)

  • 10.1007/s00454-019-00099-6

Citation Source

  • Scopus