נתן רובין

Given a finite point set P in Rd, and >0 we say that N? Rd is a weak -net if it pierces every convex set K with |K P|? ? |P|. Let d? 3. We show that for any finite point set in Rd, and any ?>0, there exist a weak -net of cardinality O(1/?d-1/2+?), where ?>0 is an arbitrary small constant. This is the first 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.