Determine if a set of points on a sphere come from a uniform distribution?

I have a large distribution of points on the unit sphere $S^2$ and I want to determine if those points came from a uniform distribution on the surface. Essentially, I'm looking for a two dimensional Kolmogorov–Smirnov test where the reference probability distribution is uniform across the sphere.

-
Any comparison based on a CDF is going to be hard to generalize to multiple dimensions, let alone to the sphere. Have you tried looking into the earth-mover distance (Wasserstein metric) or the $L_p$ distance? – John Moeller Oct 7 '13 at 18:20
@JohnMoeller I figured as much since multi-dimensional KS tests seem to be difficult (and often called into question, asaip.psu.edu/Articles/beware-the-kolmogorov-smirnov-test). I'll look into the Wasserstein metric, but I can't search for the $L_p$ distance if I don't know its name as a word, not a symbol. – Hooked Oct 7 '13 at 18:25
Google is your friend. :-p The top result for "lp distance" or "lp metric" or "lp space" is that link. – John Moeller Oct 7 '13 at 22:26
@JohnMoeller For some reason I thought you were referring to something different. If the $L_2$ norm just the standard Euclidean distance, and the other $L_p$ norms are just a different power in the summation and the radical, how do these relate a uniform distribution across a sphere? – Hooked Oct 8 '13 at 2:06
You integrate over the sphere instead of over all of $\mathbb{R}^3$. The idea is the same, but the execution is slightly different. – John Moeller Oct 8 '13 at 3:16

Using this interpretation, there are many possible extensions to a similar distance on a sphere, it depends on your choice of range space. Obvious ones are halfspaces and circles. In both cases, the corresponding distance can be computed in polynomial time since it is combinatorially sufficient to consider all halfspaces defined by 2 data points, and for circles by the smallest enclosing (and enclosed) circle defined by 3 data points. (So $n^2$ and $n^3$ tests, respectively).
There is also a statistical line of work that essentially boils down to the likelihood ratio test over your choice of range space. It is called the "Spatial Scan Statistic" (see this software and related publications: http://www.satscan.org, the manual is actually not a bad place to start). There a way to speed the calculation up to roughly $n^2 \log n$ for circles is to only consider those that are centered on one of the data points. Intuitively, the main difference between this and the pure discrepancy version is that it essentially biases towards larger ranges causing the largest deviation so as not to be fooled by a small set of oddly placed points.