Mustafa, Nabil H.
Computing Optimal EpsilonNets Is as Easy as Finding an Unhit Set
Abstract
Given a set system (X, R) with VCdimension d, the celebrated result of Haussler and Welzl (1987) showed that there exists an epsilonnet for (X, R) of size O(d/epsilon log 1/epsilon). Furthermore, the algorithm is simple: just take a uniform random sample from X! However, for many geometric set systems this bound is suboptimal and since then, there has been much work presenting improved bounds and algorithms tailored to specific geometric set systems.
In this paper, we consider the following natural algorithm to compute an epsilonnet: start with an initial random sample N. Iteratively, as long as N is not an epsilonnet for R, pick any unhit set S in R (say, given by an Oracle), and add O(1) randomly chosen points from S to N.
We prove that the above algorithm computes, in expectation, epsilonnets of asymptotically optimal size for all known cases of geometric set systems. Furthermore, it makes O(1/epsilon) calls to the Oracle. In particular, this implies that computing optimalsized epsilonnets are as easy as computing an unhit set in the given set system.
BibTeX  Entry
@InProceedings{mustafa:LIPIcs:2019:10663,
author = {Nabil H. Mustafa},
title = {{Computing Optimal EpsilonNets Is as Easy as Finding an Unhit Set}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {87:187:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10663},
URN = {urn:nbn:de:0030drops106632},
doi = {10.4230/LIPIcs.ICALP.2019.87},
annote = {Keywords: epsilonnets, Geometric Set Systems}
}
2019
Keywords: 

epsilonnets, Geometric Set Systems 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

2019 