We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Near-Linear Algorithms for Geometric Hitting Sets and Set Covers.
- Authors
Agarwal, Pankaj K.; Pan, Jiangwei
- Abstract
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 (N polylog (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 .
- Subjects
ALGORITHMS; DATA structures; POINT set theory; APPROXIMATION algorithms
- Publication
Discrete & Computational Geometry, 2020, Vol 63, Issue 2, p460
- ISSN
0179-5376
- Publication type
Article
- DOI
10.1007/s00454-019-00099-6