dnet: an approximation algorithm for hitting-set 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 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. Finally, recently Agarwal and Pan 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. These together have resulted in a lack of available software for fast computation of small hitting-sets. We present dnet, a public source-code module that incorporates new improvements for the design of a fast algorithm.

  • Geometric Hitting Sets for Disks: Theory and Practice. (Norbert Bus, Saurabh Ray).
    Proc. of the 23rd European Symposium on Algorithms (ESA '15), 2015.

    You can download the source code here.