# Thread: Uniform Distribution of Points over the Surface of a Sphere

1. ## Uniform Distribution of Points over the Surface of a Sphere

Hi,

*- Is there a method for uniformly distributing an arbitrary number of points over the surface of a sphere?

To further clarify:

**- 2 Points Solution = 1 point on North pole and one on South Pole

**- 3
Points Solution = 3 points on equator separated by 120 degrees

**- 4
Points Solution = Corners of a Tetrahedron mated/projected on a sphere

**- 6
Points Solution = Corners of a Octahedron mated/projected on a sphere

2. Established Member
Join Date
Mar 2007
Posts
2,018
Here's a blog article on the subject:

http://www.xsi-blog.com/archives/115

You can also create a geodesic sphere, but the only algorithm I know of for doing that is based on recursively subdividing the faces of an icosahedron, so it won't work for an arbitrary number of points.

3. Originally Posted by a1call
*- Is there a method for uniformly distributing an arbitrary number of points over the surface of a sphere?
I notice that you skipped 5 points. Why was that?

4. Established Member
Join Date
Apr 2004
Posts
1,805
Originally Posted by a1call
Is there a method for uniformly distributing an arbitrary number of points over the surface of a sphere?
Well you have to decide precisely what you mean by being uniformly distributed, for your purposes.

Why would you accept 3 points in a planar arrangement around the equator, but (I'm guessing, since you didn't mention it) reject 5 points in a planar arrangement around the equator? After all, every point of the 5 is separated from every adjacent point by 72 degrees, which is the same as we can say for the 12 points of an icosahedron, which I am sure you would accept as uniformly distributed, so in that sense it is uniform. If you accept 5 around the equator, then you can do any number. Nonetheless, I would myself reject 5 around the equator as uniform distribution over the full surface of the sphere.*

Really I think the only options you have if you want full symmetry in your uniformity are 1, 2, 3, 4, 6, 8, 12 and 20: ie the points of the 5 regular platonic solids, plus 1, 2 and 3. Anything else would not be entirely uniform, unless you were willing to relax certain symmetries.

There are many more polyhedra, which are known as semi-regular. http://en.wikipedia.org/wiki/Semi-regular_polyhedra Only you can decide if the vertices of a semi-regular polyhedron are "uniform" enough for you. Then there are those geodesic dome structures. http://en.wikipedia.org/wiki/Geodesic_dome Are they uniform enough for you?

*5 points around the equator are separated from all of their neighbours by 72 degrees. But it fails to "populate" the whole sphere with 72 degree separations. Ie, you can find points (10 of them) which are 72 degrees from any pair of adjacent existing points, but none of these points are occupied. But for 3 points, any other point that is 120 degrees from any pair of existing points is the 3rd point. So that is a full occupation, even though it is in practice (inevitably) planar.

5. nauthiz,
Wow, I should have asked earlier. I have been tackling this problem on and off for about 3 years. The article is very useful. I am looking for the most perfect solution which basically is only satisfied by the repulsion algo among the options.

Imagine say 5 identical round bar magnets tied together by their South poles.

The formation of the North poles (in absence of external forces) is what I am looking for.

I have written my own code to simulate this. But the program fails for most numbers of points greater than 12. I am not sure why. Perhaps there are no equilibriums possible for 13 magnets or perhaps the algo keeps shifting on a loop.

hhEb09'1,

I left out 5 points because there are no regular polyhedra with 5 points and I was fishing for alternatives. My program's solution for 5 points is North pole, South pole, and 3 on the equator separated by 120 degrees. I am convinced that this is a stable formation in the bar magnets scenario.

Ivan Viehoff,

You are absolutely correct. Definitions are critical. I am looking for the most uniform possible i.e. the repulsion algo.

One surprising result of my program is that for 8 points the solution is not a cube but an anti-prism of the cube. Again, I am convinced that this would be a stable formation of magnets and not a cube.

Thank you all for the informative posts. The follow up question is:

*- Is there a repulsion algo available somewhere?

Many, Many thanks.

6. Originally Posted by a1call
hhEb09'1,

I left out 5 points because there are no regular polyhedra with 5 points and I was fishing for alternatives. My program's solution for 5 points is North pole, South pole, and 3 on the equator separated by 120 degrees. I am convinced that this is a stable formation in the bar magnets scenario.
I was kinda wondering that tells me more about what you accept as a uniform distribution.
You are absolutely correct. Definitions are critical. I am looking for the most uniform possible i.e. the repulsion algo.
One surprising result of my program is that for 8 points the solution is not a cube but an anti-prism of the cube. Again, I am convinced that this would be a stable formation of magnets and not a cube.
I'm not sure what an anti-prism of the cube is, but I imagine it's another cube!

ETA: ok googled it. So, it would be like a cube, with the top face twisted 45 degrees, sorta. How far apart are the two square faces?

7. Order of Kilopi
Join Date
Mar 2004
Posts
13,440
... or x electrons that obeyed classical electrostatics (point charges, each with identical charge) constrained to the surface of a sphere.

For 5: the coplanar arrangement is an equilibrium one (if 5 charges were placed like this they are subject to no net force), but an unstable one (the slightest disturbance will send the charges moving, to a different arrangement - would it be your two poles+3 on the equator one?).

Generalising: does the form of the 'repulsion algo' make any difference? E.g. what if repulsion scaled as the 100th power of the distance? as distance^0.01?

8. Established Member
Join Date
Mar 2007
Posts
2,018
Now I'm wondering if it might be possible for the repulsion algorithm to get stuck in a local minimum.

9. Originally Posted by hhEb09'1
I was kinda wondering that tells me more about what you accept as a uniform distribution.I'm not sure what an anti-prism of the cube is, but I imagine it's another cube!
A cube with a quarter-circle twist, actually.

This problem comes up fairly often in computer graphics. See entry 6.06 of the comp.graphics.algorithms FAQ: http://www.faqs.org/faqs/graphics/algorithms-faq/

10. Originally Posted by Nereid
... or x electrons that obeyed classical electrostatics (point charges, each with identical charge)

Generalising: does the form of the 'repulsion algo' make any difference? E.g. what if repulsion scaled as the 100th power of the distance? as distance^0.01?
That is a very good question. Fractions of actual distances would be problematic as explained in the 3rd comment in the link provided by nauthiz.
As explained there this would satisfy optimization for 1/2 the distance. For ratios greater than 1, I don't know. I will try that the 1st chance that I get.

11. Originally Posted by nauthiz
Now I'm wondering if it might be possible for the repulsion algorithm to get stuck in a local minimum.
Well, unless we find a database of the coordinates for the 1st few hundred point scenarios somewhere, then something gives.

As cjameshuff mentions this is a common issue in many applications.

12. Originally Posted by cjameshuff
This problem comes up fairly often in computer graphics. See entry 6.06 of the comp.graphics.algorithms FAQ: http://www.faqs.org/faqs/graphics/algorithms-faq/
Thanks cjameshuff,
The confirmation of antiprism over cube was there and more:
For example, eight points can be placed
on the sphere further away from one another than is achieved by
twist the top face 45 degrees about the north pole, and then
move the top and bottom points along the surface towards the equator
a bit
I will have to check for un-planarness of my solution in which case it won't be a real antiprism.

Also from the FAQ:
Jon Leech developed code to do just this. It is available at
ftp://ftp.cs.unc.edu/pub/users/jon/points.tar.gz.
sample output files for various n < 300, which may be used off-the-shelf
if that is all you need.
Unfortunately the link was broken when I checked. Will try again later maybe with the wayback archives.

13. Originally Posted by cjameshuff
A cube with a quarter-circle twist, actually.
Eighth-circle twist

14. Originally Posted by hhEb09'1
Eighth-circle twist
...
Well, it was right in my head!

Here, I've cooked up an implementation in JavaScript:
http://arklyffe.com/spherepoints.html

Requires a browser that supports the canvas tag...Firefox, Safari, and I think Opera will work. Beware of setting excessively large numbers of points...each point affects every other point, so time to execute a relaxation step scales with the square of the number of points.

15. Hi cjameshuff,

Thank you for the program.

I tried it for 13 points with otherwise default values (in Google Chrome). I then graphed the coordinate points printed on a R1 sphere. They are all on the surface of a sphere centered at 0,0,0 but the formation seems very random. How would you optimize the relaxation for a more uniform pattern?

BTW, I could be wrong but my best guess is that my program fails for larger that 12 points because of rounding errors in calculation of the great circle distances.

I have used the "atan2" function but I haven't calculated it's rounding limits.

16. Established Member
Join Date
Apr 2004
Posts
1,805
Originally Posted by a1call
One surprising result of my program is that for 8 points the solution is not a cube but an anti-prism of the cube. Again, I am convinced that this would be a stable formation of magnets and not a cube.
I can believe that a cubic antiprism maximises the "separation" of 8 points in some sense, but in an important sense is not as "uniformly distributed" as a cube. It is not as symmetric. Btw, is the separation maximised with equilateral triangular faces, which is the definition of a cubic antiprism as a semiregular solid, or is there an isoceles triangle that achieves it better?

I think that actually what you are looking for is not best described as "uniform distribution". That implies some sort of good symmetry properties, which your cubic antiprism demonstrates is not necessarily what you desire. I would call what you are looking for a "minimum energy" solution.

Clearly in the magnetic analogy, as two points come closer to each other there is an increase in "energy" as they get closer, and in the physical world they would seek a minimum energy distribution. Obviously you can "distribute" any number of points to a minimum energy solution, but there may be non-uniquenesses, or local minima you could get stuck in, in some cases. But if you were to change the formula for the increase in energy as two points got closer, I suspect you would start to get different answers.

I rather suspect that you are proposing a problem as difficult as the Kepler Conjecture. The KC is that hexagonal close packing is the maximum density packing of spheres in 3-d space. Gauss proved that hcp is the maximum density packing among symmetrical packings, the difficulty is the non-symmetrical possibilities. Toth in 1953 showed it could be reduced to checking a finite number of cases, but so many that only a computer could realistically do it. The claimed proof by Thomas Hales announced in 1998 claims to achieve that. As with the 4-colour theorem, it is likely to take some time for people to be reasonably sure that the proof is without error. http://en.wikipedia.org/wiki/Kepler_conjecture

17. Yes,
It is difficult to know if you have the right answer even when you do.
There are more than 100 solutions here. Their number 13 looks exactly like mine (and as wrong as mine). Please see 1st image.

With regards to the 8 points, I wrongly labeled/recognized it as an antiprism. It is similar but not a true antiprism. Please see the 2nd image. It does "look" uniform. The far side has the exact (I think) same pattern rotated 90 degrees.
My algo optimizes for the closest neighboring 3 points to have the maximum distance (calculated as the "great circle distance" using the atan2 function). I think this archives closest 2 neighbors at equal distances for all points.
Last edited by a1call; 2009-Feb-24 at 05:13 PM.

18. Originally Posted by a1call
I tried it for 13 points with otherwise default values (in Google Chrome). I then graphed the coordinate points printed on a R1 sphere. They are all on the surface of a sphere centered at 0,0,0 but the formation seems very random. How would you optimize the relaxation for a more uniform pattern?
For that sparse of a sphere, bump the force scaling up to 0.01.

Originally Posted by a1call
BTW, I could be wrong but my best guess is that my program fails for larger that 12 points because of rounding errors in calculation of the great circle distances.
I did not use the surface distance in my implementation...the distance used is the length of the chord, not the arc. Combined with the fact that points further along the sphere will have a resulting force vector pointing less and less along the surface of the sphere, the result should be similar.

I suspect from your description that you're doing things the hard way, using spherical coordinates. Using cartesian coordinates, dot products, and a unit-radius sphere, the great circle distance is simply acos(dot(p1, p2)).

Here's a version using the great-circle distances:
http://arklyffe.com/spherepoints2.html

It seems a bit less numerically stable, maybe because of the way I compute the force direction.

19. Originally Posted by Ivan Viehoff
Well you have to decide precisely what you mean by being uniformly distributed, for your purposes.

Why would you accept 3 points in a planar arrangement around the equator, but (I'm guessing, since you didn't mention it) reject 5 points in a planar arrangement around the equator?
The two look like different situations to me, although you seem to come to the same conclusion in the footnote. I think we must have different interpretations about what would qualify. With the 5-point case, there are the missing points you mention, but with the 3-point case, there aren't.

20. Banned
Join Date
Dec 2005
Posts
14,315
Technically, 3 isn't uniformly distributed, as some points are further away from one another than others.

Tetrahedron is the only solution.

If you remove the universally equidistant restriction, you could simply place a point centered above the face of each triangle, which in turn creates additional triangles, and so forth, an infinitum.

Thus: 4, 8, 20...

21. More details regarding the issue from a mathematicians point of view and historical relation to atomic formation.

Pretty much an echo of what Ivan Viehoff stated:
N = 8: Eight particles arrange themselves into two squares on parallel planes, with the squares rotated by 45 degrees relative to each other. The 28 separations between particles come in the following four lengths:

a = 1.2876935 b = 1.8968930 c = 1.6563945 d = 1.1712477

We observe that c = d, so the two parallel square faces have edge lengths d. This configuration has E = 19.675..., as opposed to E = 22.485... for the vertices of a cube inscribed in a sphere. This shows that the vertices of Platonic solid are not necessarily

in a stable equilibrium configuration. In other words, perfect symmetry does not imply stable equilibrium.
1st 50 visual solutions.

Number 8 looks like an antiprism and is probably not right!
Then again, here is another source showing an antiprism.

The best tool so far.
Last edited by a1call; 2009-Feb-25 at 04:03 PM.

22. Originally Posted by mugaliens
Technically, 3 isn't uniformly distributed, as some points are further away from one another than others.
It looks uniformly distributed to me. If each of the three points is separated by 120 degrees on a great circle, then each pair of the three points is 2/3*pi*r apart, and every other point on the surface is closer than this to at least one of the three points.

23. Established Member
Join Date
Apr 2004
Posts
1,805
Originally Posted by لطفيّ
The two look like different situations to me, although you seem to come to the same conclusion in the footnote. I think we must have different interpretations about what would qualify. With the 5-point case, there are the missing points you mention, but with the 3-point case, there aren't.
It depends what you mean by uniform distribution. One way of implementing the words is to say it is a uniform distribution if there is a symmetry group that enables you to move any point to any other. There is only one group of order 5, and that can only be implemented on a sphere as a rotation group around a fixed axis. So, if that is what you take uniform to mean, then that is the only uniform distribution of 5 points on a sphere. But it has drawbacks, as I note and you acknowledge.

It is now clear that a1call is interested in what would best be called minimum energy arrangements, that this is a well-known problem called the Thompson problem, and that it is not as difficult as I supposed. Plainly there is a minimum energy solution for any number of points, but it need not be unique.
Last edited by Ivan Viehoff; 2009-Feb-25 at 05:02 PM. Reason: devastating typo

24. Established Member
Join Date
Apr 2004
Posts
1,805
Originally Posted by Ivan Viehoff
I can believe that a cubic antiprism maximises the "separation" of 8 points in some sense, but in an important sense is not as "uniformly distributed" as a cube. It is not as symmetric. Btw, is the separation maximised with equilateral triangular faces, which is the definition of a cubic antiprism as a semiregular solid, or is there an isoceles triangle that achieves it better?
Looking at the N=8 case in the link you provided, I can see that the triangles are not equilateral, rather isoceles with the base slightly shorter than the equal sides.

25. Imagine say 5 identical round bar magnets tied together by their South poles.
I remember doing something like this in physics in University in respose to balancing of forces and what we perseve to be a balanced system may not look the same as the actual outcome. I can't remember the actual details but it you have to calculate the force and distance for each point to every other point on the sphere and determine it's balancing point to the forces the other points are putting on it.

I also remember that I didn't do too well in that assigment. I had a couple of big empty patches in my sphere.

26. Originally Posted by Ivan Viehoff
It depends what you mean by uniform distribution. One way of implementing the words is to say it is a uniform distribution if there is a symmetry group that enables you to move any point to any other. There is only one group of order 5, and that can only be implemented on a sphere as a rotation group around a fixed axis. So, if that is what you take uniform to mean, then that is the only uniform distribution of 5 points on a sphere. But it has drawbacks, as I note and you acknowledge.

It is now clear that a1call is interested in what would best be called minimum energy arrangements, that this is a well-known problem called the Thompson problem, and that it is not as difficult as I supposed. Plainly there is a minimum energy solution for any number of points, but it need not be unique.
I am OK with calling five points around a great circle non-symmetric, I just got the impression that you were drawing an analogy with the three point case, which looks like a different situation to me. Maybe I was just misinterpreting part of your post, because it looks like later on you also draw a distinction between the three and five point scenarios.

27. Established Member
Join Date
Apr 2004
Posts
1,805
Originally Posted by لطفيّ
I am OK with calling five points around a great circle non-symmetric,
But I'm not. 5 points around the great circle are certainly symmetric. It is the only fully symmetric arrangement of 5 points on a sphere in which there is a symmetry available that transforms any point to any other.

When I suggested to generalising 3 points around the equator to 5, it is because both have the same kind of underlying symmetry group, ie, a rotation group.

One at each pole and three around the equator is also symmetric in a way, but not fully symmetric. (The symmetry group is the non-commutative group with 6 elements - there is only one group of that description.) But it doesn't have full symmetry as none of the symmetries can move a point at a pole to a point at the equator.
Last edited by Ivan Viehoff; 2009-Feb-27 at 09:58 AM. Reason: Made a mess first time

28. Originally Posted by Ivan Viehoff
But I'm not. 5 points around the great circle are certainly symmetric. It is the only fully symmetric arrangement of 5 points on a sphere in which there is a symmetry available that transforms any point to any other.
I think I should have said "uniform" instead of "symmetric" in my last post. But here is what is confusing me about your responses.

Here you suggest that the 5-point great circle arrangement is similar to the 3-point arrangement by some criterion.

Originally Posted by Ivan Viehoff
Why would you accept 3 points in a planar arrangement around the equator, but (I'm guessing, since you didn't mention it) reject 5 points in a planar arrangement around the equator?
Then you have this explanation.

Originally Posted by Ivan Viehoff
When I suggested to generalising 3 points around the equator to 5, it is because both have the same kind of underlying symmetry group, ie, a rotation group.
But then later in the first cited post you reject five as uniform.

Originally Posted by Ivan Viehoff
Nonetheless, I would myself reject 5 around the equator as uniform distribution over the full surface of the sphere.*
The footnote explanation is in the same post.

Originally Posted by Ivan Viehoff
*5 points around the equator are separated from all of their neighbours by 72 degrees. But it fails to "populate" the whole sphere with 72 degree separations. Ie, you can find points (10 of them) which are 72 degrees from any pair of adjacent existing points, but none of these points are occupied. But for 3 points, any other point that is 120 degrees from any pair of existing points is the 3rd point. So that is a full occupation, even though it is in practice (inevitably) planar.
So this is what is confusing me. In the first quote I have made, you ask why the OP would not accept the five-point arrangement if not also accepting the three-point arrangement, but then in the fourth quote you draw a distinction between the two. So I am not sure if you would also reject the three point arrangement as uniform.

By the definition that seems natural to me, the three-point great circle arrangement is uniform, but the five-point is not. Do you have the same conclusion, or a different one? If we have a different answer, then I want to understand if the difference is in the definitions of "uniform" we are using.

29. You might do a google for "spherical codes". Essentially, a spherical code is a configuration of points on a sphere (of any number of dimensions, but I suspect you mean the ordinary sphere) that "maximizes the minimum distance between pairs of points"--what that will mean is that if there is any equally-distributed configuration, it would be a spherical code, and conversely, spherical codes will be nearly like this. The subject has been well studied (but not 100% solved), it being closely related to sphere packings, and error-correcting codes.

Of course, if there is a regular polyhedron (or even a quasi-regular polyhedron) of a given size, that produces a pretty good configuration. Quasi-regular polyhedra also do well (e.g. I think a geodesic dome is quasi-regular--I forgot the exact definition).

30. Originally Posted by tdvance
You might do a google for "spherical codes".
Thank you for the phrase. I did so and minimum angular separation will come in handy for my application.

What exactly is meant by not solved?
Is it meant to indicate that a general rule has not been formulated to calculate the minimum separation value for any given number of points?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•