Summary: 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, H. Brönnimann and M. T. Goodrich [Discrete Comput. Geom. 14, No. 4, 463–479 (1995; Zbl 0841.68122)] made an important connection of this problem to the size of fundamental combinatorial structures called \(\epsilon\)-nets, showing that small-sized \(\epsilon\)-nets imply approximation algorithms with correspondingly small approximation ratios. Very recently, P. K. Agarwal and J. Pan [“Near-linear algorithms for geometric hitting sets and set covers”, in: Proceedings of the 30th annual symposium on computational geometry, 8–11 June 2014 Kyoto, Japan. New York, NY: ACM. 271–279 (2014; doi:10.1145/2582112.2582152)] 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 \(\epsilon\)-nets for disks; unfortunately, the current state-of-the-art bounds are large – at least \(247/\epsilon\) and most likely larger than \(40/\epsilon\). Thus the approximation factor of the Agarwal and Pan algorithm ends up being more than 40. The best lower-bound is \(2/\epsilon\), which follows from the Pach-Woeginger construction [J. Pach and G. Woeginger, “Some new bounds for epsilon-nets”, in: Proceedings of the sixth annual symposium on computational geometry, 6–8 June 1990, Berkeley, CA. New York, NY: ACM 10–15 (1990; doi:10.1145/98524.98529)] for halfplanes 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/\epsilon\) 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 \(\epsilon\)-nets for a variety of data-sets are lower, around \(9/\epsilon\).