Reprint of: Weak \(\varepsilon\)-nets have basis of size \(O(1/{\epsilon}\log (1/\epsilon))\) in any dimension

DOI10.1016/j.comgeo.2007.02.007zbMath1192.68751OpenAlexW1981780371MaRDI QIDQ982945

Nabil H. Mustafa, Saurabh Ray

Publication date: 28 July 2010

Published in: Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial geometryweak \(\epsilon\)-netshitting convex sets

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Other problems of combinatorial convexity (52A37)

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