Improved bounds on weak \(\varepsilon\)-nets for convex sets

DOI10.1007/BF02574025zbMath0822.68110WikidataQ54309354 ScholiaQ54309354MaRDI QIDQ1346122

Herbert Edelsbrunner, Bernard Chazelle, Leonidas J. Guibas, Michelangelo Grigni, Micha Sharir, Ermo Welzl

Publication date: 3 April 1995

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131344

zbMATH Keywords

convex hullhyperbolic geometryweak \(\varepsilon\)-net

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items

Minimum entangling power is close to its maximum, Improved bounds on the Hadwiger-Debrunner numbers, Small strong epsilon nets, A note on stabbing convex bodies with points, lines, and flats, Further consequences of the colorful Helly hypothesis, A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space, Piercing quasi-rectangles-on a problem of Danzer and Rogers, An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets, On weak \(\epsilon\)-nets and the Radon number, A non-linear lower bound for planar epsilon-nets, Positive-fraction intersection results and variations of weak epsilon-nets, Lower bounds for weak epsilon-nets and stair-convexity, A variant of the Hadwiger-Debrunner \((p,q)\)-problem in the plane, Streaming algorithms for extent problems in high dimensions, Transversal numbers for hypergraphs arising in geometry

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decay of correlations for Hénon maps
• Points and triangles in the plane and halving planes in space
• Elementary geometry in hyperbolic space
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Nonparametric fitting of multivariate functions
• Welch's Approximate Solution for the Behrens-Fisher Problem
• Point Selections and Weak ε-Nets for Convex Hulls
• Selecting Heavily Covered Points
• Geometry. I, II. Transl. from the French by M. Cole and S. Levy