From: hollasch@kpc.com (Steve Hollasch)
Subject: Re: Distributing Points on a Sphere
Summary: Cube distribution doesn't yield even scattering
Organization: Kubota Pacific Computer, Inc.
Date: Thu, 9 Apr 1992 16:03:33 GMT


canderso@cvbnet.prime.com (Chris Anderson 4-1660 x??) writes:
> I have a need to distribute a set of n points (where n is generally >> 10)
> evenly over the surface of a unit sphere...
> My desire is to have a set of coordinates for points on the sphere
> surface with equidistant spacing and full "coverage", regardless of
> the value of n.

sgp@gpsparc.nhn.uoknor.edu (Steven G. Parker) writes:
| For each point, generate three random numbers between -1 and 1, and then
| normalize them.  This will give you a random point on a unit sphere
| in cartesian coordinates.

    This subject has been brought up before, but I haven't yet seen an
elegant solution to this problem that doesn't involve iterative
convergence.

    Anyway, since I have the benefit of having read this thread before, I
can point out that mapping random points from the volume of the unit cube
to the surface of a unit sphere does _not_ yield a uniform scattering of
points across the surface of the sphere.

    This is because a volume from the center of the cube to the midpoint
of a face is less than the volume from the cube center to a cube corner.
What happens is that you get a higher probability of generating a point
that lies by one of the cube diagonals.

    Note also that there are _two_ distinct problems of this type:

    1)  Find some function that generates a random point on the surface
        of a sphere, such that all locations on the sphere have equal
        probability.

    2)  Given n points, distribute these points "evenly" or "uniformly"
        across the surface of the sphere.

    It looks like you were thinking of problem #1, while the poster was
asking about problem #2.  If either of you disagree with this, flame-away
(I suggest you start with my odd taste in clothes).

    Going into problem #2 a bit more, I put evenly and uniformly in quotes
because I've yet to see a rigorous definition of these properties.  It's
pretty much understood what we _mean_ when we say this, but so far I've
failed to come up with a good mathematical definition of this.  By the
way, this problem is easy for 1, 2, 3, 4, 6, 8, 12, and 20 points:

        1:  Anywhere on the sphere.
        2:  Both points on each end of a diameter of the sphere.
        3:  A triangle about a great circle of the sphere.
        4:  The vertices of a tetrahedron.
        6:  The vertices of an octahedron.
        8:  The vertices of a cube.
       12:  The vertices of an icosahedron.
       20:  The vertices of a dodecahedron.

    [As an aside, this is the first time I realized that a dodecahedron
     has 20 vertices and 12 faces, while an icosahedron has 12 vertices
     and 20 faces.]

    Now with respect to platonic solids, I'm really not sure that their
vertices meet the uniformity property, because I haven't yet seen a good
definition.

    So, let's see if we can define the uniformity criterion:

        Uniform Distribution of Points on a Sphere;  Attempt 1

            Sub-definition:
                Let Dij be the chordal distance between Pi and Pj.

            A distribution of n points {P0 ... Pn} on a sphere are a
            _uniform_ distribution if for all i and j != i, min(Dij)
            is equal to some constant.

            [ In other words, for each point, find the distance to the
              nearest neighbor.  If all these distances are the same, then
              the points are uniformly distributed. ]

    This definition has a flaw - can you find it before reading on?

    The flaw is that it doesn't guarantee that the points are spread out;
if you take 100 points and stuff them into the same location, all of the
Dij's will be 0, which will satisfy the uniformity criterion as given
above.  This is also true, for example, if you put a small equilateral
triangle on the surface of the cube.

    So does anybody else have any ideas about this?

________________________________________________________________________
Steve Hollasch                             Kubota Pacific Computer, Inc.
hollasch@kpc.com                           Santa Clara, California