Point Selections and Weak ε-Nets for Convex Hulls

Noga Alon, Imre Bárány, Zoltán Füredi, Daniel J. Kleitman

Research output: Contribution to journalArticle

88 Scopus citations

Abstract

One of our results: let X be a finite set on the plane, 0 < ε < 1, then there exists a set F (a weak ε-net) of size at most 7/ε2 such that every convex set containing at least ε|X| elements of X intersects F. Note that the size of F is independent of the size of X.

Original languageEnglish (US)
Pages (from-to)189-200
Number of pages12
JournalCombinatorics, Probability and Computing
Volume1
Issue number3
DOIs
StatePublished - Sep 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Point Selections and Weak ε-Nets for Convex Hulls'. Together they form a unique fingerprint.

Cite this