Last week, we discussed how we could generate uniform random points in a triangle using a (tiny) bit of linear algebra, mostly the parallelogram rule, and a random variable uniform on . It required a tiny bit of math and was computationally very simple.
This time, let us see how we can generate uniformly distributed random points on a sphere.
At first, you may think choosing independently latitude and longitude (in polar coordinates) would do the trick, but you quickly realize, after plotting it the points, that they are inordinately numerous near the poles and comparatively sparse at the equator:
So what went wrong? Choosing both coordinates independently fails to take into account that not all latitudes have the same circumference and, accordingly, their differential area varies. Simply put: there are more points to be put on a latitude near the equator than near a pole.
So a method of mapping randomly, but uniformly spaced, points on a sphere must take this basic observation into account. Let us simplify the problem by considering we are working on a unit sphere, that is, a sphere with a radius of 1. Let us suppose that the South-North axis is the Y axis. Then the sphere goes from -1 (the South Pole) to +1 (the North Pole).
To distribute points equidistantly on the sphere, we have to know the differential surface length between two given latitude, and to do so, we will need to compute a surface of revolution (that’s calculus 201 or 301).
At height the radius of the disk perpendicular to that reaches the surface of the sphere is given by , which is just Pythagoras’ formula with for a radius of 1. The differential radius is:
The integral of the surface of revolution is between latitudes
with all possible and chosen to give equal surface, with an angle difference of . maps -1 to 1 onto with equal density, which is exactly what we need. Finally:
where, here also, is a uniform random number on the interval . We only have to compute the polar to Cartesian transformation (if we need to) for display:
And indeed, the points are uniformly distributed:
That’s a lot of work, but it was completely worth the effort.
Calculus, and math in general, is quite a powerful ally of the good programmer—even more so of the computer scientist—but it seems that many C.S. programs do not take math seriously enough. When doing my B.Sc. (maybe I wasn’t the best student ever, but that’s beside the point here) we only had 5 courses on a total of 30-something. We had a calculus course which had more or less the same contents as the two cégep courses and as such wasn’t that useful, a course on linear algebra that was also pretty dismal (I have quite a few stories about the lecturer), a course on probability and statistics, a course on statistics, and finally a course in discrete mathematics (the one I enjoyed the most, by far). Overall, it all seems a bit thin for people who will manipulate information for the rest of their lives, even if only to generate random numbers.
Let me end this digression by enjoining my readers, all of you, to question the quality and depth of your mathematical education and, if you’re still studying, to ask yourself what better math could do for you, and what means you should take to better your skills. I do that too, all the time, so it’s not like I’m saying I’m much better than you.