A non-linear lower bound for planar epsilon-nets

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

We show that the minimum possible size of an ∈-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1=∈. This settles a problem raised by Matoušek, Seidel and Welzl in 1990.

Original languageEnglish (US)
Title of host publicationProceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Pages341-346
Number of pages6
DOIs
StatePublished - 2010
Externally publishedYes
Event2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, NV, United States
Duration: Oct 23 2010Oct 26 2010

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
CountryUnited States
CityLas Vegas, NV
Period10/23/1010/26/10

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Epsilon nets
  • VC dimension
  • Weak epsilon nets

Cite this

Alon, N. (2010). A non-linear lower bound for planar epsilon-nets. In Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 (pp. 341-346). [5671197] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2010.39