Point Selections and Weak ε-Nets for Convex Hulls
From MaRDI portal
Publication:4291196
DOI10.1017/S0963548300000225zbMath0797.52004WikidataQ101133139 ScholiaQ101133139MaRDI QIDQ4291196
Noga Alon, Zoltan Fueredi, Daniel J. Kleitman, Imre Bárány
Publication date: 30 May 1994
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)
Related Items
Algorithms for ham-sandwich cuts, Counting triangle crossings and halving planes, Dynamic half-space range reporting and its applications, Improved bounds on weak \(\varepsilon\)-nets for convex sets, Bounding the piercing number, Stabbing simplices by points and flats, Helly-type theorems for the diameter, A survey of mass partitions, Improved bounds on the Hadwiger-Debrunner numbers, Hitting simplices with points in \(\mathbb R^{3}\), Piercing convex sets, Radon numbers grow linearly, A Tverberg-type result on multicolored simplices, A note on stabbing convex bodies with points, lines, and flats, From a \((p, 2)\)-theorem to a tight \((p, q)\)-theorem, Further consequences of the colorful Helly hypothesis, Theorems of Carathéodory, Helly, and Tverberg without dimension, One-Sided Epsilon-Approximants, Bounding Helly Numbers via Betti Numbers, An optimal generalization of the colorful Carathéodory theorem, An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets, Helly’s theorem: New variations and applications, Nerves, minors, and piercing numbers, An optimal extension of the centerpoint theorem, On weak \(\epsilon\)-nets and the Radon number, A non-linear lower bound for planar epsilon-nets, Upper bounds for stabbing simplices by a line, Quantitative fractional Helly and \((p,q)\)-theorems, Colourful linear programming, Positive-fraction intersection results and variations of weak epsilon-nets, Weak \(\varepsilon \)-nets have basis of size \(O(1/\varepsilon\log (1/\varepsilon))\) in any dimension, Lower bounds for weak epsilon-nets and stair-convexity, A topological colorful Helly theorem, Quantitative \((p, q)\) theorems in combinatorial geometry, Reprint of: Weak \(\varepsilon\)-nets have basis of size \(O(1/{\epsilon}\log (1/\epsilon))\) in any dimension, Radon numbers and the fractional Helly theorem, Unnamed Item, Tverberg’s theorem is 50 years old: A survey, Eppstein's bound on intersecting triangles revisited, A variant of the Hadwiger-Debrunner \((p,q)\)-problem in the plane, A new lower bound on Hadwiger-Debrunner numbers in the plane, Small weak epsilon-nets, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, No‐dimension Tverberg's theorem and its corollaries in Banach spaces of type p, Further Consequences of the Colorful Helly Hypothesis, Helly-type problems, Transversal numbers for hypergraphs arising in geometry, Algebraic \(k\)-sets and generally neighborly embeddings
Cites Work
- Supersaturated graphs and hypergraphs
- The number of triangles covering the center of an \(n\)-set
- On empty triangles determined by points in the plane
- A generalization of Caratheodory's theorem
- Points and triangles in the plane and halving planes in space
- On extremal problems of graphs and generalized graphs
- On the number of halving planes
- Partitioning with two lines in the plane
- A Generalization of Radon's Theorem
