This constant factor depends on the sizes of ϵ -nets for disks; unfortunately, the current state-of-the-art bounds are large – at least dcaadcf6098432aec547" title="Click to view the MathML source">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 [32] 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/ϵ 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 are lower, around 9/ϵ.