Can I read Tighter Estimates for epsilon-nets for Disks on EtoBox?

Tighter Estimates for epsilon-nets for Disks by Bus, Norbert; Garg, Shashwat; Mustafa, Nabil H.; Ray, Saurabh is a scholarly article available to read on EtoBox.

What is Tighter Estimates for epsilon-nets for Disks about?

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 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. Very recently, Agarwal and Pan showed that their scheme can be implemented in near-linear time for disks in the plane. Altogether this gives $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 $\epsilon$-nets for disks; unfortunately, the current state-of-the-art bounds are large -- at least $24/\epsilon$ and most likely larger than $40/\epsilon$. Thus the approximation factor of the Agarwal and Pan algorithm ends up being more than $40$. The best lower-bound is $2/\epsilon$, which follows from the Pach-Woeginger construction for halfspaces in tw

Author

Bus, Norbert; Garg, Shashwat; Mustafa, Nabil H.; Ray, Saurabh

Published

2015

Language

EN