A Non-linear Lower Bound for Planar Epsilon-nets

Research output: Contribution to journalArticle

23 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 (Proc. 6th Annu. ACM Sympos. Comput. Geom., pp. 16-22, 1990).

Original languageEnglish (US)
Pages (from-to)235-244
Number of pages10
JournalDiscrete and Computational Geometry
Volume47
Issue number2
DOIs
StatePublished - Mar 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

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