License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.87
URN: urn:nbn:de:0030-drops-106632
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10663/
Go to the corresponding LIPIcs Volume Portal

Mustafa, Nabil H.

Computing Optimal Epsilon-Nets Is as Easy as Finding an Unhit Set

pdf-format:
LIPIcs-ICALP-2019-87.pdf (0.5 MB)

Abstract

Given a set system (X, R) with VC-dimension d, the celebrated result of Haussler and Welzl (1987) showed that there exists an epsilon-net 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 sub-optimal 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 epsilon-net: start with an initial random sample N. Iteratively, as long as N is not an epsilon-net 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, epsilon-nets 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 optimal-sized epsilon-nets 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 Epsilon-Nets Is as Easy as Finding an Unhit Set}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{87:1--87:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10663},
  URN =		{urn:nbn:de:0030-drops-106632},
  doi =		{10.4230/LIPIcs.ICALP.2019.87},
  annote =	{Keywords: epsilon-nets, Geometric Set Systems}
}

Keywords: epsilon-nets, Geometric Set Systems
Collection: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 04.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI