enet: a near-linear time algorithm for epsilon-nets for disks in the plane.

The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set P of points, and a set D of geometric objects in the plane, the goal is to compute a small-sized subset of P that hits all objects in D. In 1994, Bronniman and 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. This software computes epsilon nets in near linear time for the primal set system induced by disks in the plane.

  • Tighter Estimates for Epsilon-nets for Disks. (Norbert Bus, Saurabh Ray).
    Computational Geometry: Theory and Applications, vol. 53, pp. 27-35, 2016.

    You can download the source code here.