A non-linear lower bound for planar epsilon-nets

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

7 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
PublisherIEEE Computer Society
Pages341-346
Number of pages6
ISBN (Print)9780769542447
DOIs
StatePublished - 2010
Externally publishedYes
Event2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010 - Las Vegas, United States
Duration: Oct 23 2010Oct 26 2010

Publication series

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

Conference

Conference2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010
Country/TerritoryUnited States
CityLas Vegas
Period10/23/1010/26/10

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • Epsilon nets
  • VC dimension
  • Weak epsilon nets

Fingerprint

Dive into the research topics of 'A non-linear lower bound for planar epsilon-nets'. Together they form a unique fingerprint.

Cite this