Natan Rubin: Stronger bounds for weak Epsilon-Nets

Description of video

Date: 2/5/21
Speaker :Rubin Natan

Given a finite point set P in Rd, and ϵ>0 we say that a point set N in Rd is a weak ϵ-net if it pierces every convex set K with |KP|ϵ|P|. Let d3. We show that for any finite point set in Rd, and any ϵ>0, there exists a weak ϵ-net of cardinality O(1/ϵd1/2+δ), where δ>0 is an arbitrary small constant. This is the first improvement of the bound of O(1/ϵd) that was obtained in 1994 by Chazelle, Edelsbrunner, Grini, Guibas, Sharir, and Welzl for general point sets in dimension d3.