Speaker: Pankaj K. Agarwal (Duke University)

Title: Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

Abstract:
---------
Given a finite range space S = (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 S. The first 
algorithm is a simpler variant of the Br\"onnimann-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 
several 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 2D.

Joint work with Jiangwei Pan