Improved bounds on weak ε-nets for convex sets
Bernard Chazelle, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, Emo Welzl · 1993
Let S be a set of n points in IR d . A set W is a weak "-net for (convex ranges of) S if for any T ` S containing "n points, the convex hull of T intersects W . We show the existence of weak "-nets of size O i 1 " d log fi d 1 " j , where fi 2 = 0, fi 3 = 1, and fi d 0:149 \\Delta 2 d\\Gamma1 (d \\Gamma 1)!, improving a previous bound of Alon et al. We present a deterministic algorithm for computing such a net in time n(1=") O(1) . We also consider two special cases: when S is in convex position, we prove the existence of a net of size O( 1 " log 1:6 1 " ); for the case where S consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of size O(1=").