WEAK EPSILON-NETS FOR POINTS ON A HYPERSPHERE

A weak E-net for a set of points M, is a set of points W (not necessar ily in M) where every convex set containing epsilon\M\ points in M mus t contain at least one point in W. Weak epsilon-nets have applications in diverse areas such as computational geometry, learning theory, opt imization, and statistics. Here we show that if M is a set of points q uasi-uniformly distributed on a unit sphere Sd-1, then there is a weak epsilon-net W subset of or equal to R-d of size O (log(1/epsilon) log (1/epsilon)) for M, where k(d) is exponential in d. A set of points M is quasi-uniformly distributed on Sd-1 if, for any spherical cap C sub set of or equal to Sd-1 with Vol(C) greater than or equal to c(1)/\M\, we have c(2) Vol(C) less than or equal to \C boolean AND M\ less than or equal to c(3) Vol(C) for three positive constants c(1), c(2), and c(3). Further, we show that reducing our upper bound by asymptotically more than a log(1/epsilon) factor directly implies the solution of a long unsolved problem of Danzer and Rogers.