Math @ Duke

Publications [#235350] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Pan, J, Nearlinear algorithms for geometric hitting sets and set covers,
Proceedings of the Annual Symposium on Computational Geometry
(January, 2014),
pp. 271279 [doi]
(last updated on 2018/02/21)
Abstract: Given a finite range space ∑ = (X,R), with N = X + R, we present two simple algorithms, based on the multiplicativeweight method, for computing a smallsize hitting set or set cover of β. The first algorithm is a simpler variant of the BrönnimannGoodrich algorithm but more efficient to implement, and the second algorithm can be viewed as solving a twoplayer zerosum game. These algorithms, in conjunction with some standard geometric data structures, lead to nearlinear algorithms for computing a smallsize hitting set or set cover for a number of geometric range spaces. For example, they lead to O(Npolylog(N)) expectedtime 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 R2. Copyright 2014 ACM.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

