Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235350] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Pan, J, Near-linear algorithms for geometric hitting sets and set covers, Proceedings of the Annual Symposium on Computational Geometry (January, 2014), pp. 271-279 [doi]
    (last updated on 2018/02/21)

    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 R2. Copyright 2014 ACM.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320