Generating an equidistributed net on a unit n-sphere using random rotations

Abstract

We develop a randomized algorithm (that succeeds with high probability) for generating an $\epsilon$-net in a sphere of dimension n. The basic scheme is to pick $O(n\ln (1/n)+\ln (1/\delta ))$ random rotations and take all possible words of length $O(n\ln (1/\epsilon ))$ in the same alphabet and act them on a fixed point. We show this set of points is equidistributed at a scale of $\epsilon$. Our main application is to approximate integration of Lipschitz functions over an n-sphere.

References in corpus (2)

• Sharp estimates of the spherical heat kernel
• On the distribution of random words in a compact Lie group