Improved bounds on weak -nets for convex sets

DOI10.1007/BF02574025MaRDI QIDQ1346122zbMATH OpenWikidataFDO

Authors Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Michelangelo Grigni, Micha Sharir, Emo 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

hyperbolic geometryconvex hullweak \(\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)

Recommendations

• New constructions of weak -nets
• New constructions of weak epsilon-nets
• A lower bound for weak \(\varepsilon\)-nets in high dimension
• Point Selections and Weak ε-Nets for Convex Hulls

Cites work

• scientific article; zbMATH DE number 3968520 (Why is no real title available?)
• scientific article; zbMATH DE number 3459477 (Why is no real title available?)
• scientific article; zbMATH DE number 3097933 (Why is no real title available?)
• Decay of correlations for Hénon maps
• Elementary geometry in hyperbolic space
• Geometry. I, II. Transl. from the French by M. Cole and S. Levy
• Nonparametric fitting of multivariate functions
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Point Selections and Weak ε-Nets for Convex Hulls
• Points and triangles in the plane and halving planes in space
• Selecting Heavily Covered Points
• Welch's Approximate Solution for the Behrens-Fisher Problem

Cited in

(30)

• scientific article; zbMATH DE number 739012 (Why is no real title available?)
• Small strong epsilon nets
• A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space
• Improved bounds on the Hadwiger-Debrunner numbers
• Weak \(\frac 1r\)-nets for moving points
• Small weak epsilon-nets
• An Improved Bound for Weak Epsilon-nets in the Plane
• Stronger bounds for weak epsilon-nets in higher dimensions
• Weak -nets for points on a hypersphere
• New constructions of weak -nets
• Piercing quasi-rectangles-on a problem of Danzer and Rogers
• The invariance of weak convexity conditions of \(B\)-nets with respect to subdivision
• Near-optimal generalisations of a theorem of Macbeath
• A lower bound for weak \(\varepsilon\)-nets in high dimension
• A variant of the Hadwiger-Debrunner (p,q)-problem in the plane
• On weak \(\epsilon\)-nets and the Radon number
• A non-linear lower bound for planar epsilon-nets
• A note on stabbing convex bodies with points, lines, and flats
• Weak -nets have basis of size O(1/ (1/)) in any dimension
• New Lower Bounds for ϵ-nets
• New constructions of weak epsilon-nets
• One-sided epsilon-approximants
• Transversal numbers for hypergraphs arising in geometry
• Streaming algorithms for extent problems in high dimensions
• Further consequences of the colorful Helly hypothesis
• Minimum entangling power is close to its maximum
• An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets
• On weak \(\varepsilon\)-nets and the Radon number
• Positive-fraction intersection results and variations of weak epsilon-nets
• \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets

This page was built for publication: Improved bounds on weak \(\varepsilon\)-nets for convex sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1346122)