Point Selections and Weak ε-Nets for Convex Hulls

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

doi:10.1017/S0963548300000225

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 journal › Article › peer-review

110 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/ε² 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 language	English (US)
Pages (from-to)	189-200
Number of pages	12
Journal	Combinatorics, Probability and Computing
Volume	1
Issue number	3
DOIs	https://doi.org/10.1017/S0963548300000225
State	Published - Sep 1992
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1017/S0963548300000225

Cite this

@article{6915a67e66d54268b84e6588456f80ad,

title = "Point Selections and Weak ε-Nets for Convex Hulls",

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.",

author = "Noga Alon and Imre B{\'a}r{\'a}ny and Zolt{\'a}n F{\"u}redi and Kleitman, {Daniel J.}",

year = "1992",

month = sep,

doi = "10.1017/S0963548300000225",

language = "English (US)",

volume = "1",

pages = "189--200",

journal = "Combinatorics, Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "3",

}

TY - JOUR

T1 - Point Selections and Weak ε-Nets for Convex Hulls

AU - Alon, Noga

AU - Bárány, Imre

AU - Füredi, Zoltán

AU - Kleitman, Daniel J.

PY - 1992/9

Y1 - 1992/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84971766257&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84971766257&partnerID=8YFLogxK

U2 - 10.1017/S0963548300000225

DO - 10.1017/S0963548300000225

M3 - Article

AN - SCOPUS:84971766257

SN - 0963-5483

VL - 1

SP - 189

EP - 200

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 3

ER -

Point Selections and Weak ε-Nets for Convex Hulls

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this