Point Selections and Weak ε-Nets for Convex Hulls
- 12 September 1992
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 1 (3) , 189-200
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.Keywords
This publication has 10 references indexed in Scilit:
- Points and triangles in the plane and halving planes in spaceDiscrete & Computational Geometry, 1991
- On the number of halving planesCombinatorica, 1990
- On empty triangles determined by points in the planeActa Mathematica Hungarica, 1988
- Partitioning with two lines in the planeJournal of Algorithms, 1985
- The number of triangles covering the center of an n-setGeometriae Dedicata, 1984
- Supersaturated graphs and hypergraphsCombinatorica, 1983
- A generalization of carathéodory's theoremDiscrete Mathematics, 1982
- A Generalization of Radon's TheoremJournal of the London Mathematical Society, 1966
- On extremal problems of graphs and generalized graphsIsrael Journal of Mathematics, 1964
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952