putting points on a unit sphere?
Luna Moon
I am asking this for my friend.
Is there an optimal solution for placing points on a unit sphere such
that the points satisfy certain constraints of their mutual angles.
The goal is to find the placement with maximal number of points get
placed. For example, the mutual angles need to be at least 30 degree,
etc, i.e. the cosine of the angles need to be less than certain
threshold.
Any pointers? Thanks a lot!
Chip Eastham
This is a question that comes up repeatedly
in sci.math and related newsgroups. Dave
Rusin has kindly collected material from such
posts and summarized it (and much else) here:
[Sphere FAQ -- The Mathematical Atlas]
http://www.math.niu.edu/~rusin/known-math/index/spheres.html
The most regular placements of points on a
sphere correspond to the vertices of Platonic
solids:
[Platonic solid -- Wikipedia]
http://en.wikipedia.org/wiki/Platonic_solid
However only five such configurations exist,
for n = 4,6,8,12,20 vertices.
Several approaches have been tried to get a
"nice" configuration for general n vertices.
An intuitive one is to ask for a dynamically
stable solution in which vertices "repel"
one another according to an inverse square
law, but this does not produce a stable
configuration for all n. Better definitions
are IMHO to maximize the minimum distance
between points (packing), or to maximize the
volume of the convex hull of the points inside
the unit sphere.
You can google around yourself for some links
regarding these ideas. Here are a few:
[Distributing points on a sphere -- P. Bourke]
http://local.wasp.uwa.edu.au/~pbourke/geometry/spherepoints/
(has links to some C code)
[Constructing polyhedra from repelling points on a
sphere -- S. Tatham]
http://www.chiark.greenend.org.uk/~sgtatham/polyhedra/
(has links to some Python code)
[Maximum volume arrangement of points on a sphere
-- H. Pfoertner]
http://www.randomwalk.de/sphere/volmax/
(nice ray-tracing pictures; Hugo also did max-min distance)
[sphere distribution problems -- A. Sherwood]
http://www.ogre.nu/sphere.htm
(many nice links, if you want to jump in without Google)
regards, chip
Chip Eastham
To give a narrower reading to your question,
what is the maximum number of points that
can be placed on the sphere so that the
"mutual angles" are at least A, requires a
bit of clarification about what angles are
meant.
The simplest meaning would be central
angles, i.e. that the angle is measured
between rays drawn from the sphere center
to a pair of points on the sphere. This
angle is directly related to the distance
between the points on the sphere. In fact
for a unit sphere the central angle in
radians is the spherical distance.
So the max-min distance "packings" (out
of all that was discussed in my previous
post) would be most relevant:
[Maximize minimum mutual distance of N points
on a sphere]
http://www.enginemonitoring.org/sphere/
has some ray-tracing pictures by H. Pfoertner
of the optimal packings listed here in the
"library" of 3-dimensional cases:
[Spherical codes -- N. J. A. Sloane]
http://www2.research.att.com/~njas/packings/
regards, chip
Chip Eastham
With respect to minimum (central angle) separation
of 30 degrees, Sloane's "library" gives an answer
of 48 points (49 points requiring angular separation
of 29.9235851 degrees or less).
regards, chip
Luna Moon
Hi Chip,
Thanks a lot for your help. My friend says that you are right, he was
looking for the angle that's defined by COSINE in a vector space, i.e.
with rays out from the center (0) of the coordinates.
Thanks a lot for your pointers to the readings. We will read into
those. Hopefully we could find the optimal solution (the location of
the points in terms of coordinates) in high dimensional space (lets
say 100-dim) with reasonably fast speed (this is an engineering
problem :=)
hagman
Note that in high-dim spaces, points the number of points grows very
fast
(so-called curse of dimension)
Luna Moon
Yeah, we knew that...
However, we are looking for good engineering approach, i.e.
if 100+ dimension is not feasible, we will try to be happy with 30+
dim, etc.
And we can also control the number of points by the bounds on
angles ...
Chip Eastham
Yes, it will depend on how small you will allow
the angles to get as dimension N increases, or
equivalently how close to 1 the max. cosine gets.
There are three regular polytopes in each dimension N
greater than or equal to 5: the N-simplex, the N-cube,
and its dual the N-orthoplex:
reg. polytope # of vertices max. cosine
N-simplex N+1 -1/N
N-cube 2^N 1 - 2/N
N-orthoplex 2*N 0
For more general arrangements the following recursive
approach suggests itself. An N-sphere is topologically
a cone over an {N-1}-sphere. Slice the N-sphere into
a stack of {N-1}-spheres shrinking from the equator to
radius zero at the poles, so that slices are distance
R apart sufficient to give the required angular
separation. Then pack each {N-1}-dimensional slice
with distance R separations. The construction can be
applied recursively down to 1-spheres (circles), where
the optimal packings of given distance separations are
determined explicitly.
regards, chip
Luna Moon
Hi Chip,
Thanks a lot but how does the algo you described lead to the locations
of these points (in terms of coordinates)?
We are not solving a pure math existence problem here, we are trying
to look for solutions of an engineering problem.
Thank you!
Chip Eastham
It's a concrete algorithm, giving real coordinates.
Let's do the 2-sphere (the usual sphere) as an
example. Basically we'll make some slices in
the sphere perpendicular to an axis, and place
points around the resulting circles (1-spheres).
Given a unit 2-sphere and an angle of separation
of (say) 30 degrees, we can slice the sphere into
polar points and intermediate circles at the
equator and at 30 and 60 degrees "north and south"
latitude. No point on any one slice can be closer
than 30 degrees (central angle) separation from
any point on a different slice.
Of course we can fit 12 points around the equator
that are exactly 30 degrees apart, and just one
apiece at the north and south poles. The circles
of latitude shrink in radius as we move away from
the equator, so some computation is required to
get the exact number we can place in each. At
30 degrees latitude, the radius of the circle is
cos(30) = sqrt(3)/2, but we still want points
as far apart (or farther) as the points we put
on the equator, which is 2*sin(30/2) ~ 0.517638
(sticking with angles in degrees for clarity).
Just a rough estimate, but I guess about ten
points will fit around these slightly smaller
circles. At 60 degrees latitude the circles
have shrunk to radius cos(60) = 1/2. Again a
quick guess, but I think we could fit three
points around these circles.
Count up all the points and we have 14+26 = 40.
That's meant to be a lower bound, but a concrete
placement of points. Recall the optimal number
place per Sloane et al's "library" is 48. Not
an awful bound but the algorithm may not be this
efficient in high dimensions.
We could also compute an upper bound on the
number of points possible by dividing the
surface area of the entire sphere by the area
of a "cap" of radius 30/2 degrees (since the
spherical circles around each point of this
radius should have disjoint interiors).
regards, chip
Chip Eastham
Okay, I got the 10 points at latitude 30 degrees
right, but we can actually fit 5 points (not 3)
around the circles at latitude 60 degrees. So
that improves the count of points to 44 in all.
--c
Chip Eastham
The crude upper bound mentioned above works out
to 59 points, compared to the optimum 48 points.
This upper bound is not a recursive
calculation, so it can be done quickly.
"Surface" of a unit N-sphere is 2*pi^((N+1)/2)
divided by gamma((N+1)/2):
[N-sphere -- Wikipedia]
http://en.wikipedia.org/wiki/N-sphere
would be divided by the "volume" of {N-1}-spheres
of radius sin(A/2), and take the floor of the
result to get an integer.
Luna Moon
Hi Chip,
Is the upper bound achievable?
It looks like your upper bound is the optimal solution we are looking
for?
Thank you!
Chip Eastham
In general the upper bound is not achievable.
It's a quick and dirty overestimate of the
number of points that can be placed. I'd
view it as useful from an engineering
perspective in gauging how close the lower
bound (by constructing a placement, possibly
in a more sophisticated way than outlined
above) is to the upper bound.
The specific example worked out like this:
constructed lower bound: 44
"known" optimal number: 48
calculated upper bound: 59
An engineer might look at 44 vs. 59 (not
knowing what the optimal number in between
might be) and say, wow we're at 75% of
what is almost surely an unobtainable upper
bound. Close enough to design for!
Of course if you are really concerned with
attaining the absolute optimum, then you
deserve IMHO to consider that a pure math
problem...
regards, chip
P.S. There are some relatively easy tweaks
to bring down the upper bound, and likewise
some ways to improve the construction and
the associated lower bound. But my goal
here was to walk you through how concrete
the placements of the construction are.
If you want to get into grittier details
of the computation (or if someone else is
interested), I'd be happy to email that.
Luna Moon
I thought that upper bound is achievable and hence it's an optimal
solution.
What's the A in your sin(A/2)?
How do we describe those centers of the surfaces of the cups in real
coordinate numbers?
Thank you!
Chip Eastham
Here A is the (central) angle of separation
required between points.
Unlike the construction that provides a lower
bound on the optimal number of points, the
upper bound is not constructive. It is an
observation that "cups" of angular radius
A/2 around each point in a feasible placement
must have disjoint interiors. [If not, say
point x is within angle A/2 of both y and z,
the angular separation between y and z would
be less than A.] So the surface "area" of
the sphere must be at least the surface area
of those combined "cups". [Rather than work
with the curved area of a "cup" or spherical
cap, I gave a simplified calculation using
the (flat) area of a disk. The curvature of
the "cup" makes it have greater area than a
flat disk at the base of the "cup", so the
calculation is conservative wrt obtaining
an upper bound, i.e. any error is in the
direction of increasing the upper bound.]
Hope that clears things up for you and your
friend.
regards, chip
Luna Moon
Hi Chip,
Thanks a lot and we like all three solutions.
Does the "really optimal" one lead to a constructive solution which
gives real number vectors in terms of coordinates?
If not, then we have to settle with the real number vectors generated
by the first and the third.
How good/tight are the 1st and the 3rd in high-dim space?
Yes, could you please email us a recipe of how to get the real numbers
since we are taking the engineering approach and need to be able to
program it...
Thanks a lot!