Tighter estimates for ϵ-nets for disks

详细信息    查看全文

• 作者：Norbert Bus^a ; ^{busn@esiee.fr" class="auth_mail" title="E-mail the corresponding author} ; Shashwat Garg^b ; ^{garg.shashwat@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Nabil H. Mustafa^a ; ¹ ; ^{mustafan@esiee.fr" class="auth_mail" title="E-mail the corresponding author} ; Saurabh Ray^c ; ^{saurabh.ray@nyu.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Epsilon nets ; Delaunay triangulations ; Disks ; Hitting sets
• 刊名：Computational Geometry
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：53
• 期：Complete
• 页码：27-35
• 全文大小：354 K

文摘

The geometric hitting set problem is one of the basic geometric combinatorial optimization problems: given a set P   of points, and a set D$\mathcal{D}$ of geometric objects in the plane, the goal is to compute a small-sized subset of P   that hits all objects in D$\mathcal{D}$. In 1994, Bronnimann and Goodrich [5] made an important connection of this problem to the size of fundamental combinatorial structures called ϵ-nets, showing that small-sized ϵ-nets imply approximation algorithms with correspondingly small approximation ratios. Very recently, Agarwal and Pan [2] showed that their scheme can be implemented in near-linear time for disks in the plane. Altogether this gives O(1)$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 ϵ  -nets for disks; unfortunately, the current state-of-the-art bounds are large – at least dcaadcf6098432aec547" title="Click to view the MathML source">24/ϵ$24/ϵ$ and most likely larger than 40/ϵ$40/ϵ$. Thus the approximation factor of the Agarwal and Pan algorithm ends up being more than 40. The best lower-bound is 2/ϵ$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/ϵ$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/ϵ$9/ϵ$.