2021/04/26 by Rubin, Natan
#05C65 #52A20 #52A35 #52C10 #52C17 #52C35 #52C45 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1
paper · doi:10.48550/arxiv.2104.12654
Given a finite point set P in \mathbb Rd, and ε>0 we say that N⊆ \mathbb Rd is a weak ε-net if it pierces every convex set K with |K∩ P|≥ ε|P|. We show that for any finite point set in dimension d≥ 3, and any ε>0, one can construct a weak ε-net whose cardinality is O^*(\frac1ε2.558) in dimension d=3, and o(\frac1εd-1/2) in all dimensions d≥ 4.
To be precise, our weak ε-net has cardinality O(\frac1εαd+γ) for any γ>0, with
αd=
\
2.558 · amp; if d=3
3.48 · amp; if d=4
(d+√(d2-2d))/2 · amp; if d≥ 5.\
This is the first significant improvement of the bound of O((1)/(εd)) that was obtained in 1993 by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl for general point sets in dimension d≥ 3.