Page 1 of 2 12 LastLast
Results 1 to 30 of 53

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

  1. #1
    Join Date
    Jun 2005
    Posts
    1,390

    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


    Thank you in advance

  2. #2
    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. #3
    Join Date
    Apr 2005
    Posts
    11,562
    Quote Originally Posted by a1call View Post
    *- 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. #4
    Join Date
    Apr 2004
    Posts
    1,804
    Quote Originally Posted by a1call View Post
    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. #5
    Join Date
    Jun 2005
    Posts
    1,390
    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. #6
    Join Date
    Apr 2005
    Posts
    11,562
    Quote Originally Posted by a1call View Post
    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. #7
    Join Date
    Mar 2004
    Posts
    13,441
    ... 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. #8
    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. #9
    Join Date
    Jun 2007
    Posts
    4,376
    Quote Originally Posted by hhEb09'1 View Post
    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. #10
    Join Date
    Jun 2005
    Posts
    1,390
    Quote Originally Posted by Nereid View Post
    ... 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. #11
    Join Date
    Jun 2005
    Posts
    1,390
    Quote Originally Posted by nauthiz View Post
    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. #12
    Join Date
    Jun 2005
    Posts
    1,390
    Quote Originally Posted by cjameshuff View Post
    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
    the vertices of an inscribed cube: start with an inscribed cube,
    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.
    See his README file for more information. His distribution includes
    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. #13
    Join Date
    Apr 2005
    Posts
    11,562
    Quote Originally Posted by cjameshuff View Post
    A cube with a quarter-circle twist, actually.
    Eighth-circle twist

  14. #14
    Join Date
    Jun 2007
    Posts
    4,376
    Quote Originally Posted by hhEb09'1 View Post
    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. #15
    Join Date
    Jun 2005
    Posts
    1,390
    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. #16
    Join Date
    Apr 2004
    Posts
    1,804
    Quote Originally Posted by a1call View Post
    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. #17
    Join Date
    Jun 2005
    Posts
    1,390
    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.
    Attached Images Attached Images
    Last edited by a1call; 2009-Feb-24 at 05:13 PM.

  18. #18
    Join Date
    Jun 2007
    Posts
    4,376
    Quote Originally Posted by a1call View Post
    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.


    Quote Originally Posted by a1call View Post
    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. #19
    Join Date
    Feb 2009
    Posts
    27
    Quote Originally Posted by Ivan Viehoff View Post
    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. #20
    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. #21
    Join Date
    Jun 2005
    Posts
    1,390
    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. #22
    Join Date
    Feb 2009
    Posts
    27
    Quote Originally Posted by mugaliens View Post
    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. #23
    Join Date
    Apr 2004
    Posts
    1,804
    Quote Originally Posted by لطفيّ View Post
    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. #24
    Join Date
    Apr 2004
    Posts
    1,804
    Quote Originally Posted by Ivan Viehoff View Post
    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. #25
    Join Date
    Feb 2009
    Posts
    1,232
    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. #26
    Join Date
    Feb 2009
    Posts
    27
    Quote Originally Posted by Ivan Viehoff View Post
    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. #27
    Join Date
    Apr 2004
    Posts
    1,804
    Quote Originally Posted by لطفيّ View Post
    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. #28
    Join Date
    Feb 2009
    Posts
    27
    Quote Originally Posted by Ivan Viehoff View Post
    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.

    Quote Originally Posted by Ivan Viehoff View Post
    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.

    Quote Originally Posted by Ivan Viehoff View Post
    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.

    Quote Originally Posted by Ivan Viehoff View Post
    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.

    Quote Originally Posted by Ivan Viehoff View Post
    *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. #29
    Join Date
    Apr 2006
    Posts
    4,181
    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. #30
    Join Date
    Jun 2005
    Posts
    1,390
    Quote Originally Posted by tdvance View Post
    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?

Similar Threads

  1. Discussions about School uniform
    By Spoons in forum Off-Topic Babbling
    Replies: 56
    Last Post: 2011-Feb-02, 10:49 PM
  2. Momentum Experienced On the Surface Of a Rotating Sphere
    By zenbudda in forum Science and Technology
    Replies: 42
    Last Post: 2010-Jul-14, 07:18 AM
  3. Comparing the relationship between the volume & surface area of a sphere
    By grnegz in forum Space/Astronomy Questions and Answers
    Replies: 12
    Last Post: 2009-Nov-20, 01:41 PM
  4. Uniform accelerated motion under SR
    By abcdefg in forum Against the Mainstream
    Replies: 12
    Last Post: 2009-Oct-30, 03:33 AM
  5. Does the Universe look uniform to all observers?
    By Perikles in forum Space/Astronomy Questions and Answers
    Replies: 5
    Last Post: 2009-Jun-28, 04:25 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
here
The forum is sponsored in-part by: