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

DOI10.1016/j.comgeo.2007.02.006zbMath1135.68054OpenAlexW2038910763MaRDI QIDQ2479477

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)

Related Items

Tighter estimates for \(\epsilon\)-nets for disks ⋮ k-Centerpoints Conjectures for Pointsets in ℝd ⋮ Journey to the Center of the Point Set ⋮ Small strong epsilon nets ⋮ 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 ⋮ Centerpoints and Tverberg's technique ⋮ On a problem of Danzer ⋮ On a Problem of Danzer ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

Cites Work

• Unnamed Item
• \(\epsilon\)-nets and simplex range queries
• Piercing convex sets and the Hadwiger-Debrunner \((p,q)\)-problem
• New constructions of weak \(\varepsilon\)-nets
• Equipartition of mass distributions by hyperplanes
• Point Selections and Weak ε-Nets for Convex Hulls
• Improved bounds on weak ε-nets for convex sets