Weak -nets have basis of size O(1/ (1/)) in any dimension

DOI10.1016/J.COMGEO.2007.02.006MaRDI QIDQ2479477zbMATH OpenOpenAlexFDO

Authors Nabil H. Mustafa, Saurabh Ray

Publication date 26 March 2008

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2007.02.006

zbMATH Keywords

combinatorial geometryhitting convex setsweak \(\varepsilon\)-nets

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Recommendations

• Reprint of: Weak \(\varepsilon\)-nets have basis of size \(O(1/{\epsilon}\log (1/\epsilon))\) in any dimension
• A lower bound for weak \(\varepsilon\)-nets in high dimension
• Stronger bounds for weak epsilon-nets in higher dimensions
• Almost tight bounds for -nets
• Tight lower bounds for the size of epsilon-nets
• Tight lower bounds for the size of epsilon-nets
• An Improved Bound for Weak Epsilon-nets in the Plane
• New Lower Bounds for ϵ-nets
• New constructions of weak -nets
• Improved bounds on weak \(\varepsilon\)-nets for convex sets

Cites work

• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• Equipartition of mass distributions by hyperplanes
• Improved bounds on weak ε-nets for convex sets
• New constructions of weak -nets
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• Point Selections and Weak ε-Nets for Convex Hulls
• -nets and simplex range queries

Cited in

(12)

• On a problem of Danzer
• Tighter estimates for -nets for disks
• Small strong epsilon nets
• \(k\)-centerpoints conjectures for pointsets in \(\mathbb{R}^d\)
• A lower bound for weak \(\varepsilon\)-nets in high dimension
• On a problem of Danzer
• A note on stabbing convex bodies with points, lines, and flats
• Journey to the Center of the Point Set
• Centerpoints and Tverberg's technique
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• 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

This page was built for publication: Weak \(\varepsilon \)-nets have basis of size \(O(1/\varepsilon\log (1/\varepsilon))\) in any dimension

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