Article 36111 of comp.graphics:
Newsgroups: sci.math,comp.graphics,alt.graphics
From: hahn@newshost.lds.loral.com (Karl Hahn)
Subject: Re: tessellating spheres
ReplyTo: hahn@lds.loral.com
Organization: Loral Data Systems
Date: Tue, 22 Jun 1993 00:39:19 GMT
In article jensk@hpbbn.bbn.hp.com (Jens Kilian) writes:
> > Does there even exist a solution for n equally spaced
> > points on a sphere? If there does exist a solution, I would
> > like to know it. If there doesn't exist a solution, I would like
> > to know an algorithm that gives a close approximation.
>
> The vertices of a Euclidean polyhedron should give you equally spaced points
> on the enclosing sphere. Unfortunately, there aren't too many of these ...
Depending upon how you wish to define "equally spaced," it can be very
easy to show that Euclidean solids are the only solutions for more than
three points not all in the same plane.
If you require that each pair of points have equal distance between
them, then the vertices of a tetrahedron clearly form the only solution.
If you mean that each point is surrounded by neighbors that are all
equally distant from the chosen point, and from one to the next, and
that distance is the same regardless of which is the chosen point,
consider the following argument:
Place the sphere tangent to a plane, with the point of tangency being
one of the points of the equidistant set. Allow a rotation axis of
the sphere to be normal to the plane. Then there must be an n way
symmetry of the n points that are neighbors to the tangent point, and
that symmetry must be a symmetry of rotation about the axis. This
same symmetry must exist regardless of which point is chosen as the
tangent point.
This is clear because if you chose one of the neighbors of the
original tangent point as a new tangent, the distance between
these two is unchanged. Thus, the same situation exists and
so must the same symmetry. By induction over the graph formed
by all the points, you can extend this reasoning to all of them.
The spherical triangle formed by the tangent point and two adjacent
neighbors must follow the rules of spherical triangles. If d is the
equidistance and A is the angle the two arcs make at the tangent point,
then we have (assuming sphere of unit radius):
cos d = cos^2 d + (sin^2 d * cos A)
which simplifies to:
cos d = 1/(1  cos A)  1
A must be 2pi divided by an integer in order to maintain symmetry.
Let that integer be n. n > 6 results in cos d > 1, so that is
impossible. n = 6 results in cos d = 1 or d = 0 or pi. d = 0 is
clearly not a solution to the original problem, and d = pi is the
trivial case of two points at opposite poles. Solutions for n = 5,
n = 4, and n = 3 correspond respectively to the regular icosahedron,
the regular octahedron, and the regular tetrahedron respectively.
Note that these are the Euclidean solids whose faces are triangles.
The cube and the dodecahedron do not satisfy the original conditions
given above.

 (V)  "Life is indeed darkness save when there is
 (^ (`>  urge, and all urge is blind save when there
 ((\\__/ )  is knowledge, and all knowledge is vain save
 (\\< ) der Nethahn  when there is work, and all work is empty
 \< )  save when there is love."
 ( / 
   Kahlil Gibran
 ^ 
Article 36180 of comp.graphics:
From: michaelr@spider.co.uk (Michael S. A. Robb)
Newsgroups: sci.math,comp.graphics,alt.graphics
Subject: Re: tessellating spheres
Date: 23 Jun 93 13:09:32 GMT
Organization: Spider Systems Limited, Edinburgh, UK.
In article jensk@hpbbn.bbn.hp.com (Jens Kilian) writes:
>> Does there even exist a solution for n equally spaced
>> points on a sphere? If there does exist a solution, I would
>> like to know it. If there doesn't exist a solution, I would like
>> to know an algorithm that gives a close approximation.
>
>The vertices of a Euclidean polyhedron should give you equally spaced points
>on the enclosing sphere. Unfortunately, there aren't too many of these ...
>
Actually, there are around 75+. These include the Euclidean polyhedra and
more complex objects from the combination of regular polygons (triangles,
squares hexagons and octagons). If this matches your requirements you can
get a sofware package called KALEIDO which will generate vertex coordinates
for all the shapes. However, you will have to massage the object data in
order to be able to perform polygon rendering (backface culling).
kaleido  Computation and 3D Display of Uniform Polyhedra. Mirrored in
wuarchive.wustl.edu [128.252.135.4]
"graphics/graphics/packages/kaleido"  *kaleido*
Author: Dr. Zvi Har'El,
email: rl@gauss.technion.ac.il
If you want some other exotic spherical polyhedra, you can also search the
directory "/netlib/graphics/polyhedra" in "research.att.com" which contains
a large database of such objects in a simple ASCII 3Dobject description
format. There are around 180+ such objects, all of which can be used to
perform polygon rendering (However, not all are centred at the origin, which
makes animation a bit tricky).
research.att.com [192.20.225.2]:
/netlib/graphics  *SPD package*,
~/polyhedra" *polyhedra databases*.
(If you don't have FTP, use the netlib automatic mail replier: UUCP 
research!netlib, Internet  netlib@ornl.gov. Send one line message
"send index" for more info, "send haines from graphics" to get the SPD)
Further details can be found in the graphics FAQ list.
Cheers,
Michael

 Michael S. A. Robb  Tel: +44 31 554 9424  /\ _____ /\
 Software Engineer  Fax: +44 31 554 0649  //\\/ O O \//\\
 Spider Systems Limited  Email:  // ~\ \_/ /~ \\
 Edinburgh, EH6 5NG  michaelr@spider.co.uk  _// ~~~~~ \\_
Article 3848 of comp.graphics.algorithms:
Newsgroups: comp.graphics.algorithms
Path: kpc!news.kpc.com!decwrl!olivea!uunet!news.mtholyoke.edu!news.smith.edu!orourke
From: orourke@sophia.smith.edu (Joseph O'Rourke)
Subject: Re: How to equidistribute some points on a sphere?
MessageID: <1994Mar7.135523.4146@sophia.smith.edu>
Organization: Smith College, Northampton, MA, US
References: <2l4iru$rh1@lehtori.cc.tut.fi> <1994Mar7.024651.10837@sophia.smith.edu>
Distribution: inet
Date: Mon, 7 Mar 1994 13:55:23 GMT
Lines: 24
In article ,
Gary L Snethen wrote:
>In <1994Mar7.024651.10837@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes:
>
>>And let the entire mathematical community know, as the minimal energy
>>configuration of points is only known for a few values of n. It is a
>>longunsolved problem.
>
>Really? I figured that the solution was complex, but not that the problem was
>unsolved. [...]
For n = 5, 6, 7, the minimum energy configurations form double pyramids;
for n= 8, 10, 12, 14, the points are at N & S poles and antiprisms
between. Results are also known for n = 9, 11. This problem is more
commonly known as the electron problem, for obvious reasons. See p.165 in
the book below.
@book{cfgupg90
, author = "H. P. Croft and K. J. Falconer and R. K. Guy"
, title = "Unsolved Problems in Geometry"
, publisher = "SpringerVerlag"
, year = 1990
}
From: hollasch@kpc.com (Steve Hollasch)
Subject: Re: How to equidistribute some points on a sphere?
Summary: Distribution of eight points
Organization: Kubota Pacific Computer, Inc.
Date: Fri, 18 Mar 1994 01:48:17 GMT
k150337@lehtori.cc.tut.fi (Kuukkanen Petri) writes:
 How can I equidistribute n points on a sphere's surface? With 4, 6, 8, 12
 or 20 points this really is simple: just use the corners of tetrahedron,
 cube, octahedron etc.
Steve Hollasch (hollasch@kpc.com) wrote:
: No, it's not that simple. For eight points, using the vertices of a cube
: is the wrong answer. The correct one is a box with one face twisted 45
: degrees parallel to the opposite face.
In article mtaylor@dcs.qmw.ac.uk (Taylor) writes:
> I agree, and would go further and say that maximum distance shapes are
> always made out of triangles, (though not always equilateral,of course)
meyersd@cs.washington.edu (David Meyers) writes:
 The original post by Kuukkanen Petri was correct: the vertices of a cube
 ARE uniformly spaced on the surface of a sphere.
Then it would seem that we are arguing for different definitions of
"uniformly distributed".
 Consider:

 1) The vertices ... are cospherical ...

 2) Each vertex ... has 3 nearest neighbors, ... equidistant

 3) Traversing great circles on a sphere doesn't change part 2 ...

 4) ... the distance between any nearneighbor pair of points is the same.

 Sounds uniformly distributed to me.
By your definition then, there are several solutions that meet the above
criteria you use.
A) Place all points coincident at a single point on a sphere.
B) Divide N points into two sets, and place each set, coincident, at
opposite poles of the sphere.
C) For N points, space them equally around any circle on the surface of
the sphere.
As I've posted before, the definition that I prefer to use is that a
uniform distribution of points of a sphere is such that the minimum
distance between any two points in the set is maximized. The vertices
of a cube do not meet this criteria since you can space them further
apart.
 5) If you rotate one face of a cube as suggested, keeping it in the same
 plane (I assume that is what Steve Hollasch means in his message),
 each vertex of the cube has 4 "nearest neighbors", but they are NOT
 equidistant...
 Doesn't sound uniformly distributed to me.
No, as another poster noted, once you rotate one of the opposite faces,
you are free to move the faces closer together, which allows you to
enlarge the faces, which increases the distance to the nearest neighbor.
Also, I prefer to define "nearest neighbors" as the set of points that
are the minimum distance from a given point. By this definition, all
nearest neighbors are equidistant from a given point.
 6) Perhaps you can modify the shape of this "twisted cube" (actually a
 decahedron with two square facets connected by 8 triangular facets)
 to achieve uniform distribution, I'll wait for the solution. On the
 other hand, parts 14 above show that the cube's vertices satisfy the
 uniform distribution requirement quite well.
If you write an energyminimization program to model this, you'll see
that an initial state of a cube winds down to the distribution I have
given. The vertices of a cube are NOT in equilibrium. I have a program
for this which I've not gotten around to releasing (I know, I should).
Anyway, if you wish to prove this to yourself, calculate the repellent
force vector for a given vertex of a cube.
WAITAMINUTE!!!
YOW! I'm wrong! I just did this by examination and it appears that the
cube configuration is a false minima that Sloan (?) has wondered about!
I stand by my original statement that it's not an energyminimizing (or
nearestneighbormaximizing or uniform or whatever) solution, but it
does seem to be a stable configuration.
On further thought, any solution with equallyspaced points around a
circle on the sphere is also a false minima! This is getting to be
pretty interesting. So now there are infinitely many false (local)
minima in the set of energyminimizing solutions for eight points. I
hadn't thought of this before. For both these cases, the circle and the
cube, if you perturb any point by an infinitesimal amount, it should
arrive at the twisted face solution I've described (which I believe to be
the global minima of solutions). Does anybody else agree with this?
______________________________________________________________________________
Steve Hollasch Kubota Pacific Computer, Inc.
hollasch@kpc.com Santa Clara, California
Newsgroups: comp.graphics.algorithms
From: rec@arris.com (Roger Critchlow)
Subject: Re: How to equidistribute some points on a sphere?
Organization: Arris Pharmaceuticals
Date: Mon, 21 Mar 1994 17:49:44 GMT
In article kaoskat@dcs.qmw.ac.uk (franklin) writes:
Sorry to get off the mathematical pedantry (no flames please  postgrad
mathematician myself), but a couple of suggestions for the original
poster. Not for a mathematically pure solution, but just something
better than choosing points at random.
Well, here is some mathematical pedantry, and a plug for a book
(Croft, Hallard. T, et al., Unsolved Problems in Geometry, Springer
Verlag, NY, 1991) that I like:
D7. The problem of Tammes. What is the largest diameter a_n of n
equal circles that can be placed on the surface of a unit sphere
without overlap? How must the circles be arranged to achieve this
maximum, and when is there an essentially unique arrangement? These
questions were first raised by the botanist Tammes in 1930 in
connection with the distribution of pores on pollen grains.
This problem has an enormous literature; an account is given in the
book by Fejes T\'oth. The exact solution is known only for n <= 12
and n = 24. For other values of n, various upper and lower bounds
for a_n have been obtained, but many of these could certainly be
improved. The table below lists the known values of a_n, given as
the angle subtended at the center of the sphere, and indicates the
the corresponding extremal configurations.
n a_n extremal

2 180 opposite ends of a diameter
3 120 equilateral triangle in an
equatorial plane
4 109 28' regular tetrahedron
5 90 regular octahedron less on point
(nonunique)
6 90 regular octahedron
7 77 52' (unique configuration)
8 74 52' square antiprism
[ ... ]
The book referred to appears to be:
L. Fejes T\'oth, Lagerungen in der Ebene, auf der Kugel und in Raum,
2nd ed., Springer, Berlin, 1972.
And there are 34 more references given with the article.
 rec 
Newsgroups: comp.graphics.algorithms
From: dasher@netcom.com (Anton Sherwood)
Subject: antiprisms
MessageID:
Date: Sun, 27 Mar 1994 08:18:13 GMT
In article <2mdig8$rjk@gap.cco.caltech.edu>,
Charles Fu wrote:
>In article <1994Mar18.055752.29023@kpc.com>,
>Steve Hollasch wrote:
>> ... twistedface cube formation ...
>
>Note on terminology: I believe this configuration is called, at least
>in chemistry, an "Archimedean antiprism".
More generally, you get an antiprism by setting two regular ngons
parallel but twisted by pi/n and connecting them with triangles.
A more familiar antiprism is what you get if you cut off opposite
pentagonal pyramids from an icosahedron.
From: jbuddenh@artsci.wustl.edu (Jim Buddenhagen)
Newsgroups: sci.math
Subject: Re: Points on a Sphere
Date: 22 Apr 1994 11:57:11 GMT
Organization: College of Arts and Sciences  Washington University, St. Louis, Missouri, USA
DOUGLAS ROSENZWEIG (DSRG@db1.cc.rochester.edu) wrote:
: I am faced with a 3dimensional geometry problem that I believe has a well
: known solution. I hope someone could provide a solution and/or point me to
: an appropriate textbook or journal where this problem is discussed.
: Problem:
: Distribute N points uniformly on the unit sphere.
: I am specfically interested in the angle of arc separating the
: neighboring points on the sphere.
The problem needs careful definition else there are many problems and
many solutions. Unfortunately, none is easy except for simple cases.
For Tammes problem, which is to place n points on a unit sphere so that
the closest pair are maximally separated, the exact solution is only known
for n<=12 and for n=24. The best known arrangements for n up to 90 have
been given by D. A. Kottwitz in "The Densest Packing of Equal Circles on
a Sphere", Acta Cryst.(1991) A47, 158165. His results are better than
those obtained in any of references regarding Tammes problem in Conway
and Sloan's book Sphere Packings, Lattices and Groups.
For Thompson's problem, which has to do with the arrangement on n repeling
electrons confined to the surface of a sphere (which has a different
solution than Tammes problem except for a few values of n, e.g. n=2,3,4,6,12.)
I would suggest the paper "The distribution of point charges on the surface
of a sphere" by J.R. Edmundson in Acta Cryst. A48, 1992, 6069.
This paper has figures for n up to 60.
Also see, "Extremal arrangements of points and unit charges on a sphere:
equilibrium configurations revisited", by Melnyk, T.W., Knop, O. and
Smith, W.R. in Can. J. Chem vol 55, 1977, 17451761.
[material deleted]
: Complication:
: For my purposes I will also need to limit the surface of the sphere
: on which the points are distributed. In nontechnical terms, the
: points are not allowed on a 'cap' of the sphere of a certain solid
: angle, say 4*Pi/6.
Because of this complication I would suggest you do a computer simulation.
: Thank you in advance for any help that you might be able to provide.
: Douglas Rosenzweig
: Department of Radiation Oncology
: University of Rochester

Jim Buddenhagen (jb1556@daditz.sbc.com)
Newsgroups: sci.math
From: rhh@tempel.research.att.com (Ron Hardin <928911216> 0112110)
Subject: Re: Points on a Sphere
Organization: AT&T Bell Laboratories, Murray Hill, NJ
Date: Sat, 23 Apr 1994 00:12:28 GMT
The netlib directory att/math/sloane has a lot of arrangements of points on a
sphere, in particular packings for 3,4,5d up to 130 points coverings for 3d up
to 130 points maximum volumes for 3d up to 130 points
icosahedral packings, coverings, and max volumes for up to nearly 100,000
points.
According to the news item I'm reading, you can ftp to
netlib.att.com
login as anonymous
cd netlib/att/math/sloane
or send a message to netlib@research.att.com saying
send index from att/math/sloane