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 [Discrete Comput. Geom. 14, No. 4, 463–479 (1995; Zbl 0841.68122)], H. Brönnimann and M. T. Goodrich 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. Finally, recently P. K. Agarwal and J. Pan [in: Proceedings of the 30th annual symposium on computational geometry, SoCG’14. New York, NY: Association for Computing Machinery (ACM). 271–279 (2014; Zbl 1398.68656); Discrete Comput. Geom. 63, No. 2, 460–482 (2020; Zbl 1448.68445)] showed that their scheme can be implemented in near-linear time for disks in the plane.
This current state-of-the-art is lacking in three ways. First, the constants in current \(\epsilon\)-net constructions are large, so the approximation factor ends up being more than 40. Second, the algorithm uses sophisticated geometric tools and data structures with large resulting constants. Third, these have resulted in a lack of available software for fast computation of small hitting-sets. In this paper, we make progress on all three of these barriers: i) we prove improved bounds on sizes of \(\epsilon\)-nets, ii) design hitting-set algorithms without the use of these data-structures and finally, iii) present dnet, a public source-code module that incorporates both of these improvements to compute small-sized hitting sets and \(\epsilon\)-nets efficiently in practice.
For the entire collection see [Zbl 1320.68011].