PDA

View Full Version : Uniform Distribution of Points over the Surface of a Sphere



a1call
2009-Feb-23, 03:56 PM
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

nauthiz
2009-Feb-23, 04:23 PM
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.

hhEb09'1
2009-Feb-23, 04:30 PM
*- 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? :)

Ivan Viehoff
2009-Feb-23, 04:44 PM
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.

a1call
2009-Feb-23, 05:12 PM
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.

hhEb09'1
2009-Feb-23, 05:22 PM
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 (http://en.wikipedia.org/wiki/Antiprism). So, it would be like a cube, with the top face twisted 45 degrees, sorta. How far apart are the two square faces?

Nereid
2009-Feb-23, 05:35 PM
... 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?

nauthiz
2009-Feb-23, 05:47 PM
Now I'm wondering if it might be possible for the repulsion algorithm to get stuck in a local minimum.

cjameshuff
2009-Feb-23, 06:35 PM
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/

a1call
2009-Feb-23, 08:07 PM
... 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 (http://www.xsi-blog.com/archives/115).
As explained there this (http://www.sukio.de/dump/notsoperfectpacking.gif) 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.

a1call
2009-Feb-23, 10:12 PM
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.

a1call
2009-Feb-23, 10:25 PM
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.

hhEb09'1
2009-Feb-24, 12:49 AM
A cube with a quarter-circle twist, actually.Eighth-circle twist :)

cjameshuff
2009-Feb-24, 05:25 AM
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.

a1call
2009-Feb-24, 06:00 AM
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 (http://en.wikipedia.org/wiki/Great-circle_distance#Formulas).

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

Ivan Viehoff
2009-Feb-24, 03:14 PM
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

a1call
2009-Feb-24, 03:38 PM
Yes,
It is difficult to know if you have the right answer even when you do.
There are more than 100 solutions here (http://www.research.att.com/~njas/electrons/dim3/). 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.

cjameshuff
2009-Feb-24, 05:45 PM
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.



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 (http://en.wikipedia.org/wiki/Great-circle_distance#Formulas).

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.

لطفيّ
2009-Feb-24, 06:34 PM
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.

mugaliens
2009-Feb-24, 08:51 PM
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...

a1call
2009-Feb-25, 03:08 PM
More details regarding the issue from a mathematicians point of view (http://mathpages.com/home/kmath005/kmath005.htm) 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 (http://www.enginemonitoring.com/sphere/).

Number 8 looks like an antiprism and is probably not right!
Then again, here (http://members.ozemail.com.au/~llan/dmpol.html)is another source showing an antiprism. :)

The best tool so far (http://members.ozemail.com.au/~llan/mpol.html).

لطفيّ
2009-Feb-25, 03:19 PM
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.

Ivan Viehoff
2009-Feb-25, 05:01 PM
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.

Ivan Viehoff
2009-Feb-25, 05:06 PM
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.

rommel543
2009-Feb-25, 09:35 PM
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.

لطفيّ
2009-Feb-27, 12:52 AM
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.

Ivan Viehoff
2009-Feb-27, 09:52 AM
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.

لطفيّ
2009-Feb-27, 10:55 AM
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.


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.


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.


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.


*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.

tdvance
2009-Feb-28, 12:02 AM
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).

a1call
2009-Feb-28, 01:33 AM
You might do a google for "spherical codes".

Thank you for the phrase. I did so and minimum angular separation (http://www.research.att.com/~njas/packings/index.html#I) 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?

HenrikOlsen
2009-Feb-28, 01:39 AM
It probably means there's no general formula for calculating the global minimum given the number of points.

a1call
2009-Feb-28, 01:52 AM
It probably means there's no general formula for calculating the global minimum given the number of points.

Right, just the type of stuff that I would lose sleep over.
Seems straight forward on a circle. How much more complicated can it be on a sphere.:doh:

hhEb09'1
2009-Feb-28, 01:53 AM
Thank you for the phrase. I did so and minimum angular separation (http://www.research.att.com/~njas/packings/index.html#I) will come in handy for my application.
Wasn't that page linked earlier?

Notice, that the minimum separation distance is the same for 11 points as 12 points. That's interesting.

a1call
2009-Feb-28, 02:20 AM
Wasn't that page linked earlier?

Notice, that the minimum separation distance is the same for 11 points as 12 points. That's interesting.

I might have missed that link before.

5 and 6 points also have the same 90 degrees, but there seems to be no other such duplicates.

It "appears" that for any given number of points the "maximization of minimum distances" between any/all points and their 2 closest neighbors yields equal distances. The 3rd closest neighbors are all equal to the same distance or are all equal to a single longer distance.

At least it seems so for the 1st 50 solutions from a previous link (http://www.enginemonitoring.com/sphere/index.htm):


Minimum Edges: Gold. Other (longer) Edges: Blue

ETA: This one (http://www.enginemonitoring.com/sphere/pages/pack19.htm) breaks my made-up rule. The top point's neighbors are all blue. Still there seems to be only 2 lengths between neighbors (closest 3).

mike alexander
2009-Mar-01, 08:13 PM
I sure wish I could remember my group theory course.

For the 3 point problem, all I can offer is that geometrically three points always define a plane. In this case the points are constrained to a circle, so the most symmetrical arrangement is 120 degrees apart.

If someone already made this point and it went completely over my head, I apologize. Too darned many smart people around here.

Ivan Viehoff
2009-Mar-02, 10:53 AM
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.
The problem is that "uniformly distributed on a sphere" doesn't have a formal definition. There may be some definition that is natural to you, but there isn't one to me. I merely see options and problems with them. So by taking different definitions I come to different conclusions, for the purpose of illustrating the problem. The word "uniformity" suggests some kind of symmetry. But how much symmetry do you require? It turns out that OP didn't require any at all. But if you require a certain amount amount of symmetry, as I said, then you can only distribute 5 around the equator. If you reject that (and I described a possible reason for doing so), then it is for another reason.

So if "uniformly distributed on a sphere" has a natural meaning to you, perhaps you could state that meaning in terms that are complete, unambiguous, and preferably capable of being implemented. I find it hard to set out such a definition that allows one to describe one at each pole and three around the equator to be described as uniformly distributed, except in the terms that OP has in mind, which makes no requirement of symmetry at all.

mugaliens
2009-Mar-02, 10:17 PM
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.

I should have been more precise. Three points on a sphere, located on a great circle, do not define the sphere, as they just as easily define a plane, as well as a cylinder.

Four points on a circle, however, in a tetrahedron orientation, define a sphere, and each point is equidistant from all others. This is the only integer at which both the circle is defined and all points are equidistant from all other points.

At this point, the question becomes, "At what integers can points exist such that all points are equidistance from their nearest neighbors?

HenrikOlsen
2009-Mar-02, 11:57 PM
At this point, the question becomes, "At what integers can points exist such that all points are equidistance from their nearest neighbors?

I would suspect the answer is: the number of corners in the regular, truncated regular and regular rhombic polyhedra(though that would be with some corners moved out to the surface so not the actual polyhedron), which would make it:
4, 6, 8, 12, 14, 18, 20, 24, 30, 60.
I have example placements for all those numbers.

mugaliens
2009-Mar-04, 07:44 PM
I would suspect the answer is: the number of corners in the regular, truncated regular and regular rhombic polyhedra(though that would be with some corners moved out to the surface so not the actual polyhedron), which would make it:
4, 6, 8, 12, 14, 18, 20, 24, 30, 60.
I have example placements for all those numbers.

Originally I said, "Thus: 4, 8, 20..."

I can visualize 12 and 18 (I missed 'em in my original), but I'm having a difficult time visualizing 14. 24 makes sense, as does 30 and 60. I can't visualize the last two, but it follows from number theory.

Do you have a depiction of 14 you can show me?

HenrikOlsen
2009-Mar-04, 08:29 PM
That's by taking a rhombic dodecahedron (http://mathworld.wolfram.com/RhombicDodecahedron.html) and pulling all corners out to the surface of the sphere.

tdvance
2009-Mar-04, 08:35 PM
How about a "cuboctahedron"? It has 14 sides, so it comes to mind when MugAliens askes about the 14 case--take a cube, cut off the 8 corners so the cuts go through the midpoints of the edges, and you have a solid with 6 diamond-shaped (square) faces (corresponding to the 6 original faces) and 8 triangular faces (corresponding to the 8 original corners). Now, take its dual--the dual figure has a vertex at the barycenter of each face (and that's all you really need). I think these 8+6=14 points lie on a sphere, but if not, make a sphere inscribed in the original cube (so it now goes through 6 of the points, at least), and scale the radii of the remaining 8 (with respect to the center of the sphere). Is this what you, HO, are thinking?

Todd

tdvance
2009-Mar-04, 08:36 PM
Ok--from the link--that's exactly it.

mugaliens
2009-Mar-07, 05:58 PM
That's by taking a rhombic dodecahedron (http://mathworld.wolfram.com/RhombicDodecahedron.html) and pulling all corners out to the surface of the sphere.

Ah. A square with 8 initial corners and 6 faces, with additional points pulled from each of the 6 faces to the sphere's surface coincident with the 8 initial corners.

14 points.

If you examine the left-most graphic immediately below where it states "the rhombic dodecahedron is a zonohedron and a space-filling polyhedron," you'll observe the following facts:

1. The corners of the original cube are 4-sided pyramids.

2. The corners of the points extended from the faces are 5-sided pyramids.

3. As depicted, all points do not lie coincident with the surface of the same sphere! The corner points occupy a sphere with radius < radius of the sphere containing the extruded face points.

Check my math, but I'll bet you a wet loofa I'm right.

a1call
2009-Mar-08, 01:57 AM
You might be right about that particular polyhedron, but the Rhombic Dodecahedron itself is a pretty shape with 14 vertices which all do lie on the surface of a sphere. I believe that is what HenrikOlsen was referring to.

The shape is not a regular polyhedron because some vertices are the corner to 3 sides and some to 4 sides.

ETA: I stand corrected, It turns out the "rhombi" that I drew are not coplanar (flat). I can't seem to be able to make all points on the surface of a sphere if the diamonds are planar.

a1call
2009-Mar-08, 05:28 AM
This (http://perfext.com/virtual/sphere-14/)is pretty much the same geometry except that the diamonds are not planar (i.e they consist of a diamond bent into 2 triangles). All the points are on the surface of the sphere. All the triangles are equal and isosceles.

Notes:

*- Left click and drag to rotate

ETA: It looks like it ended up exactly like this old-thing (http://www.enginemonitoring.com/sphere/pages/pack14.htm).

mugaliens
2009-Mar-08, 04:57 PM
Something's missing here...

Probably these:


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

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.

Sounds to me like each of these points are equidistant from their nearest neighbors. This become important, so I clarified this, here:


At this point, the question becomes, "At what integers can points exist such that all points are equidistance from their nearest neighbors?

I'll say it this way:

2 points - each point is on the sphere, at the poles, equidistant from one another in all directions. The points do not define a sphere.

3 points - each point is on the sphere, at the equator, equidistant from one another in the closest direction. The points do not define a sphere.

4 points - each point is on the sphere, one at the north pole, with three others located 120 degrees from the point at the North Pole and one another. Thus, all points are equidistant from one another in all directions. The points define a sphere.

5 points - impossible to achieve equidistance.

6 points - each of three points lies along a line of latitude in the upper hemisphere, with the other three in the same, but southern latitude in the lower hemisphere, but 60 degrees out of longitudinal phase with the upper three. The points define a sphere.

But are all the points equidistant from one another?

7 points - impossible to achieve equidistance

8 points - impossible to achieve equidistance

etc. Basically, I don't think that beyond 6 points universal equidistance is possible, if it's even possible with 6 points; 4 may be the limit.

The next mode of operation involves being equidistant from one's nearest neighbors. To that end, I originally thought placing a point at the center of each of the triangles of a tetrahedron would allow us to continue this without end, but after looking at it, I was wrong. Further progression requires different groupings of points.

a1call
2009-Mar-08, 06:15 PM
Something's missing here...

To that end, I originally thought placing a point at the center of each of the triangles of a tetrahedron would allow us to continue this without end, but after looking at it, I was wrong. Further progression requires different groupings of points.

I think you were not totally wrong. You don't get equilateral triangles by breaking an equilateral triangle into 3 triangles("placing a point in the center"). However you do get equilateral triangles by breaking an equilateral triangle into 4 pieces. This can be continued indefinitely on a sphere.

See the applet at GEODESIC DOMES (http://www.grunch.net/synergetics/domes/domegeo.html) describing/showing this. However this does not work for an arbitrary number as stated earlier by nauthiz in the 2nd post.

I would make the following observational rule which is subject to proof or rejection:

For any arbitrary number n, points can be placed on a sphere that are the n vertices of a polyhedron with faces made of one or two groups of triangles A and B such that:

*- All A's are equal and equilateral

*- All B's are equal and isosceles

*- In some solutions these triangles can be coplanar and form more-sided faces such as here (http://www.enginemonitoring.com/sphere/pages/pack24.htm).

ETA: A simpler way of saying the same thing is that the lengths of edges of the polyhedron are all equal to either some L1 or some other L2. In some (rare) cases L2 = L1.

mugaliens
2009-Mar-09, 12:22 AM
I think you were not totally wrong. You don't get equilateral triangles by breaking an equilateral triangle into 3 triangles("placing a point in the center"). However you do get equilateral triangles by breaking an equilateral triangle into 4 pieces. This can be continued indefinitely on a sphere.

See the applet at GEODESIC DOMES (http://www.grunch.net/synergetics/domes/domegeo.html) ...

Of course! Why did I get so wrapped up around points?

So, to continue with the symmetricals (number of vertices):

4 - tetrahedron

6 - octahedron

8 - hexahedron (cube)

12 - icosahedron

20 - dodecahedron

etc.

However, with respect to a quad-divided tetrahedron, it follows:

4 - tetrahedron

10 - ?

etc.

hhEb09'1
2009-Mar-09, 05:44 PM
6 points - each of three points lies along a line of latitude in the upper hemisphere, with the other three in the same, but southern latitude in the lower hemisphere, but 60 degrees out of longitudinal phase with the upper three. The points define a sphere.

But are all the points equidistant from one another?
All points are the same distance from four other points, the fifth it is the square root of two times that distance--just the diangonal of a square.
The next mode of operation involves being equidistant from one's nearest neighbors. Obviously, all sets of points satisfy that criteria :)

I would make the following observational rule which is subject to proof or rejection:

For any arbitrary number n, points can be placed on a sphere that are the n vertices of a polyhedron with faces made of one or two groups of triangles A and B such that:

*- All A's are equal and equilateral

*- All B's are equal and isosceles

*- In some solutions these triangles can be coplanar and form more-sided faces such as here (http://www.enginemonitoring.com/sphere/pages/pack24.htm).

ETA: A simpler way of saying the same thing is that the lengths of edges of the polyhedron are all equal to either some L1 or some other L2. In some (rare) cases L2 = L1.I can prove that. :)

Of course, the n=2 and n=3 are special cases, that I'm going to throw out, since everyone seems to be happy with them anyway. :)

Just take two of the n points and place them at the antipodal poles. Then space the remaining (n-2) points out around the equator. L1=180, and L2=360/(n-2). QED. :)




Of course! Why did I get so wrapped up around points?Points and faces can be duals of each other.


So, to continue with the symmetricals (number of vertices):

4 - tetrahedron

6 - octahedron

8 - hexahedron (cube)

12 - icosahedron

20 - dodecahedron

etc. For instance, if you were to take the twenty faces of the icosahedron and place a point in the middle of each face, those twenty points would define a dodecahedron, and vice versa. Same for octahedron and cube. The tetrahedron is its own dual.


However, with respect to a quad-divided tetrahedron, it follows:

4 - tetrahedron

10 - ?

etc.I did some looking around at the polydedra classification pages on the net. I have one question. Was the great disnub dirhombidodecahedron (http://en.wikipedia.org/wiki/Great_disnub_dirhombidodecahedron) really discovered by the chief structural engineer of the World Trade Center?

a1call
2009-Mar-09, 06:49 PM
Just take two of the n points and place them at the antipodal poles. Then space the remaining (n-2) points out around the equator. L1=180, and L2=360/(n-2). QED. :)




Actually, You might be on the right track. I think from that it should be possible to conclude that the condition would hold true for "maximizing the minimum distances" solution (at least for the solutions which have the 2 poles occupied a similar proof could be used where one pole is occupied). But the details are beyond me at the moment.

hhEb09'1
2009-Mar-09, 07:46 PM
Actually, You might be on the right track. I think from that it should be possible to conclude that the condition would hold true for "maximizing the minimum distances" solution (at least for the solutions which have the 2 poles occupied a similar proof could be used where one pole is occupied). But the details are beyond me at the moment.Let's see, what's our target? If you take the area of the sphere, it's 4pi steradians. If each point is to be in its separate region, centered at the point, and we've maximized that distance, we'd get each point centered in a circle of radius 2/(sqrt(n)). Of course, that's impossible, since circles don't pack that well, and areas of "circles" on a sphere are not really pi*r2, but it's something to shoot for.

a1call
2009-Mar-09, 08:04 PM
I was thinking something much more simple. It should be possible to prove that maximizing minimums from one row (equator) to 2 would keep the condition valid. Same for 3 rows .... and thus for any possible solution. There are gaps in the proof to be filled but intuitively sounds correct to me.

a1call
2009-Mar-23, 08:04 PM
A bit of correction is required for the sake of accuracy.
It turns out that geodesic solutions do not provide "maximizing-the-minimum-distance" solutions.
Despite their name they are produced from regular polyhedron 2D faces, subdivided and then projected on a sphere . As such they are not made of true geodesics/great-circles.
See Wiki entry (http://en.wikipedia.org/wiki/Geodesic_dome).
Subdividing equilateral triangles to smaller and equal equilateral triangles works on 2D triangles but not on spherical triangles.
So Mugs you were correct.:whistle: