Article 36111 of comp.graphics: Newsgroups: sci.math,comp.graphics,alt.graphics From: hahn@newshost.lds.loral.com (Karl Hahn) Subject: Re: tessellating spheres Reply-To: 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, e-mail: 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 3D-object 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 | E-mail: | // ~\ \_/ /~ \\ | 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? Message-ID: <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 >>long-unsolved 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{cfg-upg-90 , author = "H. P. Croft and K. J. Falconer and R. K. Guy" , title = "Unsolved Problems in Geometry" , publisher = "Springer-Verlag" , 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 co-spherical ... | | 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 near-neighbor 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 1-4 above show that the cube's vertices satisfy the | uniform distribution requirement quite well. If you write an energy-minimization 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 energy-minimizing (or nearest-neighbor-maximizing or uniform or whatever) solution, but it does seem to be a stable configuration. On further thought, any solution with equally-spaced 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 energy-minimizing 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 - post-grad 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 anti-prism [ ... ] 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 Message-ID: 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: >> ... twisted-face 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 n-gons 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 3-dimensional 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, 158-165. 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, 60-69. 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, 1745-1761. [material deleted] : Complication: : For my purposes I will also need to limit the surface of the sphere : on which the points are distributed. In non-technical 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 <9289-11216> 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