Norbert Bus

Tighter Estimates for epsilon-nets for Disks

The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set $P$ of points, and a set $\mathcal{D}$ of geometric objects in the plane, the goal is to compute a small-sized subset of $P$ that hits all objects in $\mathcal{D}$. In 1994, Bronniman and Goodrich made an important connection of this problem to the size of fundamental combinatorial structures called $ε$-nets, showing that small-sized $ε$-nets imply approximation algorithms with correspondingly small approximation ratios. Very recently, Agarwal and Pan showed that their scheme can be implemented in near-linear time for disks in the plane. Altogether this gives $O(1)$-factor approximation algorithms in $\tilde{O}(n)$ time for hitting sets for disks in the plane. This constant factor depends on the sizes of $ε$-nets for disks; unfortunately, the current state-of-the-art bounds are large -- at least $24/ε$ and most likely larger than $40/ε$. Thus the approximation factor of the Agarwal and Pan algorithm ends up being more than $40$. The best lower-bound is $2/ε$, which follows from the Pach-Woeginger construction for halfspaces in two dimensions. Thus there is a large gap between the best-known upper and lower bounds. Besides being of independent interest, finding precise bounds is important since this immediately implies an improved linear-time algorithm for the hitting-set problem. The main goal of this paper is to improve the upper-bound to $13.4/ε$ for disks in the plane. The proof is constructive, giving a simple algorithm that uses only Delaunay triangulations. We have implemented the algorithm, which is available as a public open-source module. Experimental results show that the sizes of $ε$-nets for a variety of data-sets is lower, around $9/ε$.