path: root/reference/sphere.faq

		TOPICS ON SPHERE DISTRIBUTIONS

[Latest version of 1998/02/26 by Dave Rusin, rusin@math.niu.edu.
This file is available by FTP (or gopher) at 
	ftp://math.niu.edu/pub/papers/Rusin/known-math/95/sphere.faq
but I recommend instead this URL which gives links to some related areas:
	http://www.math.niu.edu/~rusin/known-math/index/spheres.html
If you're reading this, send me your comments and suggestions.]

I'm writing this FAQ because of the frequency with which topics related
to this subject appear in the USENET newsgroups such as sci.math. This
isn't really my main area of interest so some of the comments are
pretty simple-minded; if you are a power user in need of guidance, you
should look elsewhere for suggestions, while conversely if you can
offer expert guidance I'd like to incorporate it here. Some of the
material already here is lifted from other sources; whenever possible
I try to assign the blame^H^H^H^H^H credit to someone else.

The overall main topic is the question of how to place points on the 
sphere, or how to divide up the sphere into regions, in a regular way.
Along the way we'll talk about map-making, Platonic solids, and so on.
The following questions will be addressed (other suggestions welcome):

Q0. Notation
Q1. What does it mean to place  N  points "evenly" on a sphere?
Q2. Are there some values of  N  which are better than others?
Q3. How can you describe locations on a sphere, anyway?
Q4. Can you give a quick approximation to a good distribution? (*)
Q5. How can we improve an approximate solution? (*)
Q6. What if I want randomly to place points with a uniform distribution?
Q7. Can this be generalized to higher-dimensional spheres?
Q8. How is this related to collections of linear subspaces?
Q9. Where can I get the coordinates of the vertices of the Platonic solids?
Q10. How come this sounds like sphere packing?

(*) Fetch the accompanying file sphere.bas for a BASIC program demonstrating
these techniques.

Other topics possibly to include in the future:
	What's the formula for the volume of the n-ball? n-sphere?
	What's this I hear about exotic differentiable structures on spheres?
	Can you describe projective space and its relation to spheres?
	What are sources for further information?
If you need some information about these topics, let me know; that will be
my clue that it's time to add something to the FAQ.

At some point I may separate this into a 2-sphere FAQ and a hi-dimensional-
sphere FAQ. If this seems important, let me know and I'll move it up my
priority list. 

dave

==============================================================================
	ANSWERS TO THE FREQUENTLY-ASKED QUESTIONS
==============================================================================

Q0. Notation 
Just in case there is some confusion I'll informally make the definitions
I'll need later.
	EUCLIDEAN SPACE  (or n-space, or R^n) is the set of n-tuples of
real numbers. We will use the ordinary metric (distance function). Note
that we commonly speak of ourselves as living in 3-space.
	The  SPHERE  of radius  r  in  R^n  is the set of points whose
coordinates satisfy x1^2+...+xn^2=r^2; the unit sphere is the sphere of
radius  1.  Note that I am explicitly assuming all spheres are centered
at the origin. The interior of the sphere is called the  BALL  in  R^n;
it is the set of points of distance less than  r  from the origin. (The
ball and the sphere are disjoint; their union is sometimes called the
n-DISK .) If not otherwise specified we are usually referring to the sphere or
ball in  R^3.
	The  DIMENSION  of a (reasonable) subset of  R^n  is the number of
independent directions one can travel in the set. For example, in the 
ordinary sphere motion at most points is a combination of movements
East and North, so the sphere in R^3  is two-dimensional (not three).
The ball in  R^n  is n-dimensional.
	Note that the circle is the sphere (of dimension 1) in  R^2;
the sphere in R^1 is two points (+1 and -1). We often write S^n for the
n-dimensional sphere (in R^(n+1).)
	A  LINE  is the set of multiples of a point or vector (other
than the origin).  Note in particular that I am referring only to lines
thru the origin.  A  PLANE  is the set of linear combinations of two
non-collinear vectors.  (Don't call it a  SURFACE ; that's usually
understood to be anything 2-dimensional, including planes, the
2-sphere, paraboloids, and so on.)  Likewise we can take any k
linearly independent vectors in R^n and look at all linear
combinations of them; this set is called a  LINEAR SUBSPACE  of R^n and
is of dimension k.  When k=n-1, the set is called a  HYPERPLANE.

	The focus of this document is on S^2 but from time to time I
consider greater generality when it is easy to do so.

==============================================================================

Q1. What does it mean to place  N  points "evenly" on a sphere?

Well, what do you want it to mean? Several valid interpretations exist;
they lead to slightly different distributions of points.

If you want all distances between distinct points in the set to be equal,
you can have at most  4  points. Indeed, it's easy to see any 3
equally spaced points mark an equilateral triangle and any 4 must then
mark a regular triangular pyramid. You can have a 5th point equidistant
from the first  3 (glue two such pyramids face to face) but then the
4th and 5th points are too far apart.

But everyone agrees that the vertices of a regular polygon are equally
spaced in S^1, so there must be another definition we have in
mind. One can ask that every point have some property, such as being
equidistant from its nearest neighbor. Such distributions exist -- for
example, one can space the points equally along the equator of the
sphere. Still, this is not likely to be what we have in mind when we
ask for a uniform distribution of the points.

One might ask that the points be arranged "symmetrically" on the sphere in
some way; in Q3 we'll discuss how to do this, but true symmetry is available
only for a few values of  N.

It is more helpful to measure uniformity not point-by-point but by considering
some aggregate measure of the dispersion. For example, we could let  D be
the minimum distance between any pair of distinct points in the set. This
provides a measurement of how good or poor a distribution we've chosen.
For example, four points equally spaced on the equator have  D=sqrt(2)=1.41...
whereas four points on the pyramid have a larger  D=(2/3)sqrt(6)=1.63...
So we might ask for an arrangement on the sphere which maximizes  D.

In general this statement of the problem guarantees a solution exists.
Let  D  be any continuous function of  N  points on the sphere; then since
the sphere is compact, so is the Cartesian product of  N  copies of it,
so that  D  is a continuous function on a compact set, and so achieves a
maximum and a minimum. If  D  is chosen intelligently, the values of the
variables that lead to an extreme value of  D  will give an arrangement of
points which is arguably "uniform".

There are some drawbacks with this perspective. For one, the extreme
values of D will be attained more than once. (Certainly if D depends
symmetrically on the points, any permutation of the N variables will
provide another occurrence of the extreme value. Indeed, it is
reasonable to consider only functions defined on the symmetric product
S^N(S) =(SxSx...xS)/Sym_n rather than on the Cartesian product
(SxSx...xS) of N copies of the sphere S) If D is invariant under
rotations of the sphere, which is reasonable, then in order to hope to
have an isolated extreme configuration, one needs to hold one point
fixed at, say, the North pole, and to allow another point to vary only
along a meridian attached to the pole.

Another obstacle is that there are several natural choices for  D, and an
arrangement of points which is optimal for one such function need not be
optimal for another. Here are some natural choices for D:
	D1=min_i min_{j<>i} dist( Pi, Pj )   (the function considered above)
	D2=(1/N) Sum_i min_{j<>i} dist( Pi, Pj ) ("average dist to a neighbor")
	D3=Sum_i Sum_{i<>j} 1/dist( Pi, Pj ) ("potential energy")
If an electron is placed at each of the points, D3 is the sum of the
electrostatic potentials at these  N  electrons; they would tend to spread
apart if possible so as to minimize  D3.

Finally, there is the question of how one would compute an optimal 
configuration once a decision is made of how optimality would be measured.
If  D  is a differentiable function of the coordinates of the points, then
the problem can be solved with Lagrange multipliers, but this is hopelessly
cumbersome for any but the smallest values of  N  and the simplest
functions  D. Moreover, some of the most natural functions  D  to take are
not differentiable everywhere. We shall return to this in Q5.
==============================================================================

Q2. Are there some values of  N  which are better than others?

You bet! As has been pointed out above, values of N <= 4 have very natural
solutions. In addition, there are solutions for some  N  related to the
Platonic solids. Here's why.

Suppose we had an arrangement of  N  points with the following property:
given any two points there is a rotation of the sphere which 
	(1) carries the one to the other and in the process 
	(2) carries each of the points in the distribution to some other point 
		in the set (possibly itself). 
These rotations generate a group (a subgroup of SO(3) ) of
permutations of the N points; since the only rotation of the sphere
which fixes two points not antipodal to each other is the identity
(the trivial rotation), the group of all these rotations is finite
(unless N=2).

Well, as it happens, there are not many finite subgroups of SO(3).

First, there are all the cyclic subgroups which are sets of rotations
with a common axis, as well as the dihedral groups which adjoin one
rotation about an axis perpendicular to this one. If this is the
symmetry group of your arrangement of points, then all your points
lie on one circle (two circles, if you have a dihedral group and a
non-equatorial arrangement). 

The remaining finite subgroups of SO(3) are the symmetry group of the
pyramid (isomorphic to Alt(4), it has order 12), the symmetry group of
the cube (it's the full symmetric group of order 24, permuting the 4
diagonals) and the symmetry group of the dodecahedron (the symmetric
group of order 120). The octahedron is dual to the cube and the
icosahedron is dual to the dodecahedron, while the tetrahedron
(pyramid) is self-dual.  (Here "dual" means vertices of one are
midpoints of faces of the other, so dual polyhedra have the same
symmetry group.)  (For a full analysis of the Platonic solids, see
Coxeter, "Introduction to Geometry", Wiley (NY) 1969.)

It's not quite true that a set of points permuted by one of these three
groups has to be the set of vertices of a Platonic solid (as a glance
at a soccer ball [non-US: football] will show). However, a firm
insistence that there be sufficient rotations to carry each vertex
to any other limits the number of points to 120.

So there are only finitely many non-circular arrangements with this high 
degree of symmetry. Of course, you could relax the condition that there be
rotations preserving the set of points which permute the points
transitively (any point can be carried to any other one). For example, you
could begin with one of the Platonic solids and mark off, say, the
midpoint of each edge as well as each of the vertices. (The former need
to be scaled of course to make them lie on the sphere.) There is a large
collection of figures that exhibit some partial symmetry. In general, the
more symmetry you require, the fewer the number of values of  N  which
you can expect to place so symmetrically.

If you are working with spheres of a higher dimension, there are more
finite groups of rotations; the orbits of a point under these groups will
give sets of points which could reasonably be called "uniform". Indeed,
given any set of points on a sphere (or any other metric space) you can
define the Voronoi region of each point to be the set of elements in the
sphere closer to that point than to any other. Then if the rotation group
acts transitively on the points, it provides enough motions to show that
all the Voronoi regions are congruent. A couple of theorems are relevant
here, I guess: first, given any group  G  there is a group of rotations
in  SO(n)  isomorphic to  G  as long as  n  is sufficiently large. Second,
given any  n  there may be infinitely many finite subgroups in SO(n)
(as the cyclic subgroups of SO(3) demonstrate) but there are only finitely
many quotient groups  G / Z(G); that is, the  G  will have an (Abelian)
center of bounded index.

Departing from these geometric considerations, we will see in Q4 that
some approximate constructions of uniform arrangements are a little
easier for some N's than others, so if you have some freedom in the
selection of N you can make your job a little easier.

==============================================================================

Q3. How can you describe locations on a sphere, anyway?

Clearly any point on a sphere also sits in the ambient Euclidean space,
and so may be specified by its ordinary Cartesian coordinates. But these
coordinates are bound by the equation of the sphere, and it is sometimes
preferable to use coordinates which are unbound.

Since the sphere in  R^n is (n-1)-dimensional, it is natural to try to 
parameterize your position with just  n-1 variables. This is well known
on the ordinary 2-sphere, where we use latitude and longitude. Such
parameterizations are possible, although there are some nettlesome points
to keep in mind.

Ideally, a parameterization of the n-sphere would be a function P
defined on a subset of Euclidean space R^n and taking values in the
n-sphere, having the following properties:
	1) P is continuous (i.e. a continuous change in  R^n  should yield
		a continuous change on the sphere. Equivalently,  P 
		should be given by  (n+1)  continuous coordinate functions
		whose squares sum to  1. )
	2) P is one-to-one: a point on the sphere shouldn't show up more
		than once during the parameterization.
	3) P has a continuous inverse  F, that is, a coordinate function
		which determines for each point in the sphere what values
		of the parameters are needed to map to that point.
		The existence of such an  F  implies  P  would be onto.
	4) P (and/or  F)  preserves important geometric information like 
		angles or areas (or the n-dimensional equivalents).
	5) P (and/or F)  is differentiable.
Unfortunately, for topological reasons there can be no function P
meeting even just (1) (2) and (3). This is well-known to map-makers
trying the case n=2: any map of the earth's surface has to rip the 
surface somewhere.

However, there are functions which meet some of these conditions; various ones
are appropriate under different conditions.

1. If you only want to parameterize _part_ of the sphere, you
can get away with a simple projection: use  F(x1,...,x{n+1})=(x1,...,xn)
and  P(x1,...,xn)=(x1,...,xn, sqrt(1-x1^2-...-xn^2) ). Use the negative
square root to parameterize the bottom half of the sphere. If you need
to have a parameterization valid a neighborhood of some point on the
equator, have  F  drop out some other coordinate  (which  P  puts
back in with a similar square root formula).

2. You can get a correspondence P mapping onto all of the sphere
except one point (say, the North pole "NP"); indeed you can define 
P : R^n --> S-{NP} and an inverse map F going the other way which are
continuous, differentiable, one-to-one, and onto. Do this with
stereographic projection: place the plane thru the equator of the
sphere and draw rays emanating from the North Pole and pointing
downward some non-zero amount. Each such ray intersects both the
sphere and the plane in one point, and all the points in S-{NP} and
R^n are so met.  These rays then set up the one-to-one
correspondence. The formulas are
	P(x1,...,xn) = t.(x1,...,xn,0) + (1-t)(0,...,0,1)
	F(x1,...,x{n+1})= r . (x1, ..., xn)
(where (0,...,0,1) is the North Pole on the n-sphere in  R^{n+1}.) Here
t is chosen to make the distance from the origin be  1 : t=2/(1+x1^2+...+xn^2).
Also  r  is chosen to invert the first formula: r=1/(1-x{n+1})

These formulas are the basis of the polar projection used by map-makers.

3. If it is necessary to have a parameterization which preserves area
(or its n-dimensional equivalent), this coordinate system  F  can be
modified by adjusting the function  r=r(x{n+1}). 

Here's how we decide what the right function  r  is. Consider the set of
points in  S^n  with  x{n+1}=a. This is an (n-1) sphere with radius 
h=sqrt(1-a^2). Then for small  e  the set of points in  S^n  with 
x{n+1} lying between  a  and  a+e is a slightly bent version of the
product of an (n-1)-sphere of radius  h  and an interval of length 
e.sqrt[1+(dh/da)^2] = e/sqrt(1-a^2). The function  F  above carries it
to another such product, but this time the radius is  z(a)=r(a)h(a) and
the length of the interval is about e.z'(a). Since F changed the radius 
by a factor  z(a)/h, the (n-1)-volume will change by a factor
of  [z(a)/h]^(n-1). If we want to keep the  n-volume unchanged, we need
the ratio of the lengths of the interval, roughly  z'(a) sqrt(1-a^2), to
be the reciprocal of this, that is, we need   z'(a).z(a)^(n-1) =
h^(n-1)/sqrt(1-a^2) = sqrt(1-a^2)^(n-2). Solving this differential
equation shows we need 
  r(a) = z(a)/h(a) = [1/sqrt(1-a^2)].[n.integral(1-a^2)^(n/2-1) da]^(1/n)
(As z(-1)=0, the integral should be selected to vanish at a=-1.)

So  r(x)=[1/sqrt(1-x^2)].[n. integral_{-1}^{x} (1-a^2)^(n/2 - 1) da]^(1/n).
For  n=2, this gives  r(a)=sqrt(2/(1-a)), i.e. z(a)=sqrt(2*(1+a)). In
particular, this will map the whole sphere to the disk of radius 2,
whose area is then 4pi (the area of the sphere) as it should be.

4. There are also trigonometric parameterizations.
For example, it is easy to parameterize the 1-sphere (the circle) with a
parameter  t  using  P(t) = (cos(t), sin(t)). Here if we really want P
to be one-to-one we need to restrict to an interval such as  [0, 2 pi).
This is then indeed one-to-one, onto, and continuous (even differentiable)
and as a bonus preserves lengths. But there can be no continuous inverse
function. F(x,y)=arctan(y/x) will do if branches of the arctan function 
are chosen appropriately, but no set of choices can be made consistently
in all quadrants of  S^1.

Still, this parameterization is useful, and admits generalization. The
function  
	P(u,v) = (cos(u)cos(v), cos(u)sin(v), sin(u)) 
is also differentiable, maps onto S^2, and is one-to-one on the set 
(-pi/2,pi/2)x[0,2 pi). (The image of  P  on this set misses the poles, 
however.) This  P  has an inverse in the sense we had on the circle: 
(u,v)=F(x,y,z)=(arctan(z/sqrt(x^2+y^2)), arctan(y/x) ). 
	This is the ordinary parameterization of the sphere in terms of 
latitude (u) and longitude (v). By computing the Jacobian for the change of 
variable to spherical coordinates, we see that this parameterization 
changes areas by a factor of  |cos(u)|.

This may be generalized to the n-sphere: use the function  P_n, where
P_n(u1,...,un) = ( cos(un)*P_{n-1}(u1,...,u{n-1}) ,  sin(un) )
(for each  un  in (-pi/2, pi/2), the parameterization traces out an
(n-1)-sphere using P_(n-1). ); n-dimensional volume is reduced by a
factor of  | cos(u2) . cos(u3)^2 . ... . cos(un)^(n-1) |.
(I'll discuss another interpretation of this product in Q6.)

These parameterizations form the basis of various cylindrical maps of
the earth (rectangular maps excluding the poles in which the left and
right edges represent the same points on earth). The Mercator projection
is chosen to remove the distortion of angles; thus (locally) the
Mercator projection gives an accurate representation of shapes. But the
correction used is precisely the inverse of what is needed to correct
the |cos(u)| change in area, so that the Mercator projection is wildly
inaccurate at portraying areas (especially near the poles). I believe
the 'Peters projection' is the name of the map which corrects areas (but
which amplifies the distortions of angles, and thus of shapes).

5. If the trigonometric expressions are too computation-intensive, 
one can use a parameterization requiring only rational functions. Note first
that the circle may be parameterized using a variation of stereographic
projection:
	P(t) = ( -2t/(1+t^2) , (1-t^2)/(1+t^2) )
	F(x,y)= (y-1) /x
Thus, we can replace all sine/cosine pairs with these two functions.
For example, the 2-sphere may be parameterized:
P(u,v)=( 4uv/[(1+u^2)(1+v^2)], -2u(1-v^2)/[(1+u^2)(1+v^2)], (1-u^2)/(1+u^2) )
F(x,y,z)= ( (z-1)/sqrt(x^2+y^2), (y-1)/x )

For further details, consult an advanced calculus text; look up the
change-of-variables theorem, particularly spherical coordinates and
the role of the Jacobian (derivative) in determining areas.
[I'll add a reference to the mathematics of map-making as soon as I find one.]

==============================================================================

Q4. Can you give a quick approximation to a good distribution?

Of course. Mark off  K  equal segments along a meridian using  K-1
points plus the two endpoints. These segments have length pi/K. If you
swing this around the sphere, you'll mark off  K-1  circles. Now, in
spherical coordinates, these circles are the points with  
ui=-pi/2 +i*(pi/K), where  i = 1, 2, ..., K-1. They have radius  cos(ui), 
hence length 2pi*cos(ui). Thus you can divide them into about 
[2pi*cos(ui)]/[pi/K] segments as long as the segments on the meridian.
So take  Mi  to be an integer near 2*K*cos( -pi/2 + i*(pi/K)) =
2*K*sin( i * (pi/K) ), and mark off points that have  u=ui and 
v=j*(2*pi/Mi) for  j = 1, 2, ..., Mi. This will give you
2+Sum{i=1,...,K-1} M_i points on the sphere.

To within an error less than  K-1,  this is the same as 
2+Sum 2*K*sin( i* pi/K ) = 2 + 2*K*cot( pi / 2K ). For large values of  K,
this is about (4/pi) K^2.  (With an area of 4pi on the whole sphere, 
this leaves an area of (pi/K)^2 around each point, which is not
surprising since initially the points are about pi/K apart on a 
roughly square grid).

If you have the luxury of placing _approximately_ N points on the
sphere, begin with  K  an integer roughly equal to  sqrt((pi/4)N), and
compute the number of points which would be placed with the method
above; you should get about  N  points. Here are the values I get
for the first few  K  using round() to convert to integers when necessary:
for K=1, N=2; for K=2, N=6; then for subsequent  K (thru K=22), I get N=
12,22,34,46,82,106,128,156,184,214,248,288,328,368,412,460,510,562,616,...

Notice that the first layer around the north pole has about 2Ksin(pi/K)
points. For  K large, this is about  2*pi = 6.28, so we would take M1=6,
and arrange the first circle of points in the "kissing pennies" pattern.

This arrangement of points on the sphere has an obvious regularity,
but the points are not spaced as far apart as possible by any reasonable
measure -- for example, roughly sqrt(K/5) of the rows nearest the
equator will have about the same number of points in them, roughly in
a square-looking grid; clearly a honeycomb distribution will place the
same number of points with a greater spacing. This leads to question Q5.

I have included as a separate file a BASIC program which carries out this
distribution. In view of the previous paragraph, this code can be
improved when  N  is large, but I'm not really sure of an optimal way to 
do so, so I won't.

==============================================================================

Q5. How can we improve an approximate solution?

If the approximate solution in Q4 is insufficient, you'll have to decide why.
This returns you to the discussion on Q1. Let me assume that there is some
function  D  of the positions of the points which you wish to minimize
or maximize. (Replacing   D  by  -D  as necessary we may assume D is to be
maximized.)

The method outlined in  Q4  should give a low value of  D. If  D  is
differentiable, you can use the method of gradients: you adjust the positions
of the points in the direction of the gradient. Professionals in
numerical analysis should scoff at this naive approach -- for one thing,
this method assumes that the critical point is an isolated minimum; also,
it is not clear just how far in the direction of the gradient to 
proceed so as not to overshoot the region of convergence; moreover, once
in the region of convergence, the rate of convergence can be quite slow.
However, in practice I have found that if you have a moderate number of
points to place and you are not too demanding in your search for an
absolute minimum, this method works quickly enough if you begin with a
moderately uniform distribution of points. (I would appreciate learning
of improvements from numerical analysts.)

Here is what the method of gradients means in more detail.  If you
have parameterized the sphere and expressed D as a function of N sets
of the parameters, compute the partial derivatives of D with respect
to all these variables, and then evaluate at the present values of the
parameters. Add to each of the parameters a small multiple of this
partial derivative.

If instead you have calculated D as a function of the Cartesian
coordinates of the N points, you need to take the portion of the
gradient which points in a direction tangent to the sphere. In
practice, this can be accomplished by adjusting all coordinates of the
points as in the preceding paragraph, then rescaling each point's
coordinates to ensure the vector is of length one.

There is the possibility of creep to be concerned with. That is, it is
possible that with each iteration the function   D   is not improved;
rather, the points have simply all rotated somewhat around the sphere.
Under the assumption that  D  is invariant under rotations, there is no
need to allow this kind of motion. One can negate this possibility by
rotating the sphere after each iteration so that one point (say the
North pole) is returned to its previous position and another point
is returned to the meridian it was on previously.

I have put a BASIC program alongside this file to illustrate these
computations. Since the function  D  I used polls each pair of points
to find out the repulsion between them, the running time for one
iteration is proportional to  N^2. Thus I hardly recommend it for
values of  N  above a couple of hundred if you are using, say, a
personal computer.

==============================================================================

Q6. What if I want randomly to place points with a uniform distribution?

This is perhaps the easiest way: randomly select the Cartesian
coordinates independently. Toss out any sets of coordinates which take
you outside the sphere (and, should you be so unlucky, any occurrences
of the origin). Scale all the remaining points to push them out to the sphere.

Another easy way is to use the area-preserving parameterizations of
Q3. If you use the cartographer's polar projection (the third
parameterization in Q3), you need only select random points in the
disk with uniform distribution there, then map each of the selected
points onto the sphere. Of course, you'll never hit the North Pole
this way, but that event was supposed to occur with probability zero
anyway. (The simplest way to select random points in the disk is just
to pick the n coordinates separately, each randomly in [-1,1]. Then
simply discard the n-tuples not lying in the disk.)

You can also use the trigonometric parameterizations of the sphere
(the cartographer's cylindrical projections): if you are placing
points randomly, the probability that you will have to consider one of
the points where the parameterization fails to be one-to-one, or
continuous, say, is zero.

However, you need to exercise some care for spheres of dimension
greater than 1 since in that case, the trig parameterizations are not
area-preserving.  For example, if you use the spherical coordinates
above to parameterize the 2-sphere, and select u and v randomly in
their respective intervals, you'll find too many points chosen near
the poles. This is because the sets of points with u fixed near 
+-pi/2 are only _small_ circles; it is not appropriate to select these
u's as frequently.  Indeed, the frequency with which a given u is
selected should be proportional to the circumference of that circle,
which is 2pi |cos(u)|.

More generally, one can randomly select points in the n-sphere by randomly
selecting the n spherical parameters, but always remembering to select
each  u_i  with a frequency proportional to the  (i-1)-dimensional
measure of the the set of points where  u_i  is a constant. Fortunately,
we know that this set is just an (i-1) sphere whose radius is cos(u_i) 
and whose measure is then proportional to  cos(u_i)^(i-1).

Thus the problem of random point selection on the sphere reduces to this
question: how can one select values of a variable   u  from an interval
[a,b] so as to achieve a given frequency distribution  f? One way is to
let  C  be the cumulative distribution function, C(u)=integral_a^u f(t)dt.
(This is the probability that the chosen value will be between  a  and  u.)
For then if  G  is the inverse of this function, then we may select
x randomly with uniform distribution across [0,1] and let  y=G(x). This is
a random variable whose distribution function looks like this:
         Prob( h < y < h+e ) = Prob( h < G(x) < h+e )
                             = Prob(C(h) < x < C(h+e) ) which is roughly
                             = Prob( C(h) < x < C(h)+C'(h)e )
using differentials. Well, if  x  is selected with uniform distribution,
this probability is the length of that interval, namely  C'(h)e = f(h).e
since  C'=f. But to say that this original probability is roughly  f(h)e
is precisely to say that the distribution function for the variable y  is  f.

With the frequency distributions at hand, this is not difficult. The
first coordinate  u1  is selected uniformly in  [0,2 pi).  The second
coordinate  u2  is to have a probability density function  cos(u_2) /2
on (-pi/2, pi/2)  [The extra factor of  1/2  is just a scaling needed to
ensure that the cumulative distribution  C(u)  ends with  C(pi/2) = 1.0].
Indeed,  C(u) = (sin(u)+1)/2 has inverse  G(w)= arcsin(2w-1), so one can
get points uniformly on the 2-sphere using the usual trig parameterization
with  v  selected uniformly in  [0, 2pi)  and  u=arcsin(2w-1) where
w  is selected uniformly in  [0,1]. The Cartesian coordinates are then
(sqrt(4x-4x^2).cos(v), sqrt(4x-4x^2).sin(v),  2x-1).

With a slight change of variables, this can be viewed as the equal-area
cylindrical projection in cartography: you can parameterize the surface
of the 2-sphere with coordinates  x  in [-1, 1]  and  v  in [0,2 pi) 
in such a way as to preserve area by mapping  (x,v) to
(sqrt(1-x^2) cos(v), sqrt(1-x^2) sin(v), x). This is the projection 
which carries points on the sphere (minus the poles) to points on a 
cylinder wrapped around the equator by shining a light straight out from
the axis through the sphere to the cylinder.

On the 3-sphere (and higher) the next variable is selected as  u3=G(x3)
where  x3  is selected uniformly in [0,1] and  G  is the inverse of
the function  C(u) = (1/2)(u+pi/2+sin(u)cos(u)). The next variable
after that is selected similarly using  C(u) = ( cos(u) - sin^3(u)/3 - 1/3).
And so on.

Observe that if  C  can be computed, it is not necessary to be able to
solve for its inverse  G  explicitly. Instead, each of the computations of
y=G(x)  may be written  x=C(y), an equation to be solved for  y  when  x
is known. This is easily handled with Newton's method.

I believe a method of generating numbers randomly with a given distribution
is treated in Knuth's Art of Computer Programming.

==============================================================================
Q7. Can this be generalized to higher-dimensional spheres?

I have melded this into the previous questions -- anyone reading this
who can think of questions particular to higher dimensions should let me
know what ought to go in here.

==============================================================================

Q8. How is this related to collections of linear subspaces?

I put this question here because someone asked me recently about how
to parameterize the set of planes and other linear subspaces of Euclidean
space. I can't quite remember the question, so I'll not make an
answer at this point.

One comment to make is that points on the sphere (or, more precisely,
pairs of antipodal points) correspond to lines through the origin in 
R^n. The planes in  R^n  correspond similarly to great circles (circles
of maximal circumference). If  n=3,  the planes can be parameterized in
a natural way by finding the line perpendicular to them. If you
trace these correspondences through, you'll see that there is a 
natural one-to-one correspondence between great circles on the 2-sphere
and pairs of antipodal points. You can get the circle from the points
as the set of points equidistant from the pair; you can get the pair from
the circle as the only points equidistant from all elements of the circle.

More generally, there is a correspondence between the  k-dimensional
and the n-k dimensional subspaces of  R^n. The family of all k-dimensional
subspaces in  R^n  (or  n-k dimensional subspaces) is known as the
Grassmannian manifold; it is indeed a manifold and has dimension
k(n-k). When  k=1 or k=n-1, this is also known as projective n-1 space;
there is a two-to-one mapping  S^{n-1} --> RP^{n-1}  which simply sends
a point to the line it's on (this map sends antipodal points of  S^{n-1}
to the same element of  RP^{n-1} of course. This map turns  S^{n-1}
into a two-fold cover of  RP^{n-1}; for  n>2  this is the universal
covering of projective space.)

This material is often treated in graduate topology courses, particularly
in a discussion on vector bundles in an algebraic topology course.
You may wish to consult Milnor's book "Characteristic Classes"
(Princeton Univ Press), which is however not elementary.

==============================================================================

Q9. Where can I get the coordinates of the vertices of the Platonic solids?

There are 5 Platonic solids. An interesting but brief discussion (with
pictures) may be found, for example, in Gallian's  "Contemporary
Abstract Algebra",  D C Heath 1986.

Solid		Number of Vertices	# Edges		# Faces
Tetrahedron		4		6		4
Cube			8		12		6
Octahedron		6		12		8
Dodecahedron		20		30		12
Icosahedron		12		30		20

Notice the duality between certain pairs. Also note that V-E+F=2 in
all cases. This is deep, and may be thought of as the first fact in
homology theory.

I will give coordinates of these points (and in indication of the rest
of the structure) in the most compact way I know; if you want the
coordinates so that, for example, the North Pole is one of the vertices,
you'll have to rotate the coordinates (the BASIC program I include has
in it an application of this procedure.)
I have scaled the coordinates so that they lie in the unit sphere, but
this is not always the prettiest form. I have however set it up so that
the coordinates of the dual pairs reflect this duality.

Tetrahedron
The points are (0,0,1), (1/3)(2sqrt(2), 0, -1), and both points
(1/3)(-sqrt(2), +-sqrt(6), -1). All pairs are joined by an edge; all
triples (sets of three points) lie on a common face.

Cube
The 8 points are (+-c, +-c, +-c) where  c=1/sqrt(3) and the plus/minus signs
may be chosen independently. 
The 12 edges join pairs of points which have 2 coordinates equal.
The 6 faces are quadruples of points for which one of the coordinates is 
	constant.

Octahedron
The 6 vertices are of three types: (+-1, 0, 0) (0, +-1, 0) and (0, 0, +-1).
The 12 edges join all pairs except the three pairs of antipodal points.
The 8 faces consist of all triples which include one point of each type.

Icosahedron
(using some information in a post by cjhenrich@delphi.com)
The 12 vertices are of three types: (+-a, +-b, 0), (0, +-a, +-b), and
	(+-b, 0, +-a), where a=sqrt((5+sqrt(5))/10) and b=sqrt((5-sqrt(5))/10)
The 30 edges come in two flavors: there are 24 edges joining points of
	different types such that their common non-zero coordinate is of
	the same sign (e.g., (a, -b, 0) and (0, -a, b) have negative 2nd
	coordinates). There are also 6 edges joining pairs of points of
	the same type for which the sign in front of the  a  are equal
	(e.g.  (a, b, 0)  and  (a, -b, 0).)
The 20 faces are also of two general sorts: There are 8 triplets consisting
	of one point of each type such that whenever two of the points
	have a common non-zero coordinate, those coordinates are of the	
	same sign. Also, there are 12 triplets which contain two points of
	the same type having the same sign 'X' in front of the  a,  and a
	third point having   'X'.b  in that coordinate (e.g., given the
	two points at the end of the last paragraph, the third point on
	a face with them is  (b,0,+-a). )

Dodecahedron: This is dual to the icosahedron
I adapted these coordinates from a post by David Seal.
The 20 vertices include 8 vertices (+-c, +-c, +-c)  (c=1/sqrt(3)) and
	12 of the forms (+-x, +-y, 0), (0, +-x, +-y), (+-y, 0, +-x) where
	x=(sqrt(5)+1)/(2*sqrt(3)) and y=(sqrt(5)-1)/(2*sqrt(3)).
I will leave it to the reader to dualize the construction of the edges
	and vertices of the icosahedron to get the edges and faces of	
	the dodecahedron. (That means I started it but it took too long.
	The edges are the pairs of points of distance sqrt( (2/9)(sqrt(5)-1) )
	from each other.)

==============================================================================

Q10. How come this sounds like sphere packing?

Very observant of you! Actually, there are a lot of questions whose 
answers sound like an enumeration of the Platonic solids. Here is one
way to see a connection.

Suppose you have a packing of Euclidean space with spheres of radius  1.
There is a way to get evenly spaced points on the unit sphere from it.

For any r>0 let a_r be the number of spheres in the packing which are
contained in the ball of radius r centered at the origin.  Note that
if V is the volume of the ball of radius 1 in R^n, then the ball of
radius r has volume V.r^n, so we have an upper bound of a_r <= r^n.
The limit of a_r to r^n as r increases without bound is the 'packing
density' d. Thus for large r we have a_r is roughly d r^n. In
particular, there are roughly d.n.r^(n-1) balls which fit in the
sphere of radius r+1 but not in the sphere of radius r. If we take the
centers of just these balls and scale them back just a bit, we will
get roughly d.n.r^(n-1) points on the sphere of radius r.  Since the
sphere centers are of distance at least 2 from each other, the points
on the sphere will be almost 2 units apart, or further.

Scaling this picture by a factor of r,  we get about  d.n.r^(n-1) points
on the unit sphere, with distances between them not much less than
2/r. This is not really better than we achieved with the method in Q4,
but it has the advantage that we can also place points on the sphere 
corresponding to spheres in the packing which, for example, fit in
the ball of radius  r+1.5, or r+2. Possibly these points, when projected
to the sphere of radius  r, will lie close to other points already
placed, but then again, maybe not.

It is not possible, so far as I know, to go backwards and create a
sphere packing from a distribution on a sphere. The difficulty is that
a sphere packing implies a distribution of arbitrarily many points on
the sphere, and gives these distributions in a coherent way, whereas
an individual distribution is done with just one fixed number of points.

There is abundant literature and a fair amount of controversy about
sphere packings. Certainly the easiest sphere packings to understand
and use are the ones with great regularity: one places a sphere
centered at each point in a crystallographic lattice. An introduction
to these may be found, for example, in Durbin's "Modern algebra"
(Wiley, 1985). One looks at a subgroup of the group of translations in
R^n which is discrete (each group element is far from any other one);
the translates of a single point under this group form a lattice. The
group of symmetries of such a lattice is called a crystallographic
group. Note that there may be some symmetries which leave a point
fixed; the group of these is finite, and indeed there are only a few
possible groups: dropping, if necessary, to a subgroup of index two,
we can assume the group contains only rotations, at which point it
must be cyclic of order 1, 2, 3, 4, or 6; dihedral of order 4, 6, 8,
or 12, or the symmetry groups of the tetrahedron or octahedron.

This topic comes up from time to time in the popular press, during
which an interview with the inimitable John Conway is de rigueur.
There is also some very interesting work on lattices in higher
dimensions, particularly dimensions which are a multiple of 8, such as
the important Leech lattice. The book by Conway and Sloane is full of
such tidbits.

==============================================================================