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.
The KS test can be interpreted as the discrepancy (http://en.wikipedia.org/wiki/Discrepancy_theory) of the distributions where the ranges are one-sided intervals. More specifically if one distribution is an eps-approximation of the range space described by one-sided intervals, then the KS distance is eps (see here: http://geomblog.blogspot.com/2011/02/sample-complexity-for-eps.html, there is probably a better reference).
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.