| equally spaced points on a hypersphere? [message #41449] |
Fri, 29 October 2004 07:51  |
robert.dimeo
Messages: 42
Registered: November 2001
|
Member |
|
|
Hi,
I would like to create (n+1) equidistant points on an n-dimensional
sphere. The initial information provided is the center of the sphere,
the radius, and *any* point on the sphere. From that you need to find
the coordinates for the remaining n points. As a simple example,
three equidistant points on a 2-dimensional sphere (a circle), can be
located 120 degrees apart. Any hints on how to do this in general for
n-dimensions?
Thanks in advance!
Rob
P.S. This is for an extension to the Nelder-Mead downhill simplex
routine, AMOEBA.PRO.
|
|
|
|
| Re: equally spaced points on a hypersphere? [message #41524 is a reply to message #41449] |
Mon, 01 November 2004 05:34  |
robert.dimeo
Messages: 42
Registered: November 2001
|
Member |
|
|
James,
Thanks very much for your solution. This is exactly what I was
looking for. The function below implements the steps outlined in your
posting.
Rob
function create_simplex,ndim,center = center,radius = radius
; Uses a technique suggested by James Kuyper to
; create an equilateral simplex in n-dimensions. The return
; value is an array ndim by ndim+1. The coordinates of
; the i-th vertex of the simplex are obtained as
; p[*,i] such as in the following call:
; IDL> p = create_simplex(5) ; create a 5-d simplex
; IDL> vertex_3 = p[*,2] ; the 3rd vertex in the 5-d simplex
;
p = dblarr(ndim,ndim+1)
if n_elements(center) eq 0 then center = dblarr(ndim)
if n_elements(radius) eq 0 then radius = 1d
; Fill in the values for n = 2
p[0,0] = -sqrt(3.)/2. & p[1,0] = -0.5
p[0,1] = sqrt(3.)/2. & p[1,1] = -0.5
p[1,2] = 1.
if ndim gt 2 then begin
for j = 3,ndim do begin
; Solve for the value of the new dimension
p[j-1,j] = sqrt(total((p[0:j-1,1]-p[0:j-1,0])^2)-1d)
; Find the center
pc = dblarr(j)
for i = 0,j-1 do pc[i] = (moment(p[i,0:j]))[0]
; Subtract the center from each of the points
; in the simplex so that it is centered at 0
for k = 0,j do p[0:j-1,k] = p[0:j-1,k] - pc[0:j-1]
; Now find the normalization constant for unit radius
; of the hypersphere
norm = sqrt(total(p[*,0]^2))
p = temporary(p)/norm
endfor
endif
; Scale the simplex
p = p*radius
; Shift the center
for i = 0,ndim-1 do p[i,*] = p[i,*]+center[i]
return,p
end
James Kuyper <kuyper@saicmodis.com> wrote in message news:<41827538.4050709@saicmodis.com>...
>
>
> For n=1, the solution is two points at +/-1.
>
> For n>1, take the solution for n-1 dimensions, centered at the origin.
> Add one dimension, and give all those points a value of 0 in the new
> dimension. Add a point with a value of 'x' for the new dimension, with
> all it's other coordinates set to 0. Calculate the distance of the new
> point from any of the old points, as a function of 'x'. Solve for the
> value of 'x' that puts the new point at the same distance from the old
> point, as the old point was from all of the other points. By symmetry,
> the new point will also be that same distance from all of the other old
> points. Find the center of the new set of points. Shift all the points
> by the amount needed to center them on the desired location. Shift all
> of the points outward from the center by the same factor, to get a
> hypersphere of the desired radius.
>
> Example, for n=2:
>
> Start with two points a <-1,0> and <+1,0>.
> Add a third point at <0,x>. The distance from first point is
> sqrt(1+x^2). The distance between first two points is 2, so x = sqrt(3).
>
> The center of <-1,0>, <1,0> and <0,sqrt(3)> is at <0, 1/sqrt(3)>.
>
> Shifting all the points to center at 0, we get <-1,-1/sqrt(3)>,
> <1,-sqrt(3)/3> and <0,2/sqrt(3)>. The new circle has a radius of 2/sqrt(3).
>
> Multiply by sqrt(3)/2, to get a circle of radius one, leaving us with
> <-sqrt(3)/2, -1/2>, <sqrt(3)/2, -1/2>, <0,1>.
>
|
|
|
|
| Re: equally spaced points on a hypersphere? [message #41533 is a reply to message #41449] |
Fri, 29 October 2004 11:00 |
jeyadev
Messages: 78
Registered: February 1995
|
Member |
|
|
In article <cb539436.0410290651.698f65f@posting.google.com>,
Rob Dimeo <robert.dimeo@nist.gov> wrote:
> Hi,
>
> I would like to create (n+1) equidistant points on an n-dimensional
> sphere. The initial information provided is the center of the sphere,
> the radius, and *any* point on the sphere. From that you need to find
> the coordinates for the remaining n points. As a simple example,
> three equidistant points on a 2-dimensional sphere (a circle), can be
> located 120 degrees apart. Any hints on how to do this in general for
> n-dimensions?
>
> Thanks in advance!
>
> Rob
Munge around in sci.math.num-analysis and sci.match. Or even
alt.math.recreational. It should be in the archives. Turns up
now and then.
--
Surendar Jeyadev jeyadev1@wrc.xerox.com
Remove 1 for email address
|
|
|
|
| Re: equally spaced points on a hypersphere? [message #41537 is a reply to message #41449] |
Fri, 29 October 2004 10:18 |
James Kuyper
Messages: 425
Registered: March 2000
|
Senior Member |
|
|
Tom McGlynn wrote:
> Craig Markwardt wrote:
>
>> Matt Feinstein <nospam@here.com> writes:
>>
>>> On 29 Oct 2004 07:51:58 -0700, robert.dimeo@nist.gov (Rob Dimeo)
>>> wrote:
>>>
>>>
>>>> Hi,
>>>>
>>>> I would like to create (n+1) equidistant points on an n-dimensional
>>>> sphere. The initial information provided is the center of the sphere,
...
> I'm not sure what it means to have 'equidistant' points on a sphere.
> I don't think the OP wants each point to be equidistant from all
> other points -- I don't think that's possible for more than n+1 points
> in an n-dimensional space.
That's precisely what he's asking for. See above.
|
|
|
|
| Re: equally spaced points on a hypersphere? [message #41538 is a reply to message #41449] |
Fri, 29 October 2004 10:24 |
James Kuyper
Messages: 425
Registered: March 2000
|
Senior Member |
|
|
Craig Markwardt wrote:
> Matt Feinstein <nospam@here.com> writes:
>
>> I think that if 'equidistant' means that each point has the same
>> relation to -every- neighboring point, then it implies that the points
>> lie on a regular polyhedron.
>
>
> Hmm, but consider a soccer ball (truncated icosahedron). The faces
> are not all regular, and yet the nearest neighbors are all
> equidistant, no?
Nearest neighbors are equidistant, by definition. You'll never have more
than one nearest neighbor, unless all of your nearest neighbors are at
the same distance.
Of course, I know what you actually meant, though I can't quite figure
out how to express it.
However, the original question was about a set of points which are ALL
equidistant from each other. That's why the maximum is n+1, where n is
the number of dimensions.
>> In any case, a lowest energy
>> configuration may only be a local minimum with respect to small
>> variations of the positions of the points, so the global properties of
>> such a minimum are not necessarily unique.
>
>
> I think if one uses a 1/r^2 potential, then there is a single global
> minimum. I guess it's possible for the iterator program to get stuck
> elsewhere.
At the very least, if you take one solution and apply an arbitrary
rotation around the center of the sphere, or a reflection through an
arbitrary plane passing through the center of the sphere, you will
produce another solution. However, I think that there are cases with
non-trivial multiple solutions, as well.
|
|
|
|
| Re: equally spaced points on a hypersphere? [message #41539 is a reply to message #41449] |
Fri, 29 October 2004 09:52 |
James Kuyper
Messages: 425
Registered: March 2000
|
Senior Member |
|
|
Craig Markwardt wrote:
> Matt Feinstein <nospam@here.com> writes:
>
>> On 29 Oct 2004 07:51:58 -0700, robert.dimeo@nist.gov (Rob Dimeo)
>> wrote:
>>
>>
>>> Hi,
>>>
>>> I would like to create (n+1) equidistant points on an n-dimensional
>>> sphere. The initial information provided is the center of the sphere,
>>> the radius, and *any* point on the sphere. From that you need to find
>>> the coordinates for the remaining n points. As a simple example,
>>> three equidistant points on a 2-dimensional sphere (a circle), can be
>>> located 120 degrees apart. Any hints on how to do this in general for
>>> n-dimensions?
For n=1, the solution is two points at +/-1.
For n>1, take the solution for n-1 dimensions, centered at the origin.
Add one dimension, and give all those points a value of 0 in the new
dimension. Add a point with a value of 'x' for the new dimension, with
all it's other coordinates set to 0. Calculate the distance of the new
point from any of the old points, as a function of 'x'. Solve for the
value of 'x' that puts the new point at the same distance from the old
point, as the old point was from all of the other points. By symmetry,
the new point will also be that same distance from all of the other old
points. Find the center of the new set of points. Shift all the points
by the amount needed to center them on the desired location. Shift all
of the points outward from the center by the same factor, to get a
hypersphere of the desired radius.
Example, for n=2:
Start with two points a <-1,0> and <+1,0>.
Add a third point at <0,x>. The distance from first point is
sqrt(1+x^2). The distance between first two points is 2, so x = sqrt(3).
The center of <-1,0>, <1,0> and <0,sqrt(3)> is at <0, 1/sqrt(3)>.
Shifting all the points to center at 0, we get <-1,-1/sqrt(3)>,
<1,-sqrt(3)/3> and <0,2/sqrt(3)>. The new circle has a radius of 2/sqrt(3).
Multiply by sqrt(3)/2, to get a circle of radius one, leaving us with
<-sqrt(3)/2, -1/2>, <sqrt(3)/2, -1/2>, <0,1>.
>> Unfortunately, when you go to dimension greater than two, there are
>> constraints on the number of 'equidistant' points you can have on a
>> sphere. For example, in 3-D, there are (only) five regular polyhedra,
>> so n can only have the values 4, 6, 8, 12, and 20 for a tetrahedron,
>> octahedron, cube, icosahedron, and dodecahedron.
>
>
> So is there any requirement that the tesselation produce a regular
> polyhedron?
Yes. If all of the points are to be equidistant from each other, then
the object they trace out is necessarily a regular polyhedron. I fact,
there is only one polyhedron in three dimensions where all of the
vertices are equidistant from each other, and that's the tetrahedron. In
general, the maximum number is 1 more than the number of dimension of
the sphere.
All the edges of regular polyhedra are the same length, but that's not
the same thing.
> Clearly it is possible to place *any* number of equidistant points on
> a sphere via an iterative approach. As discussed on line, start
> with random placement of points, allow the points to repel each other,
> iterate until you reach the lowest energy configure.
That can't produce an equidistant set of points for any n more than 1
higher than the number of dimensions. In three dimensions it also can't
produce a regular polyhedron for any n other than the ones that were
listed above. Try it with 5 points on the surface of a three-dimensional
sphere. The precise configuration you'll end up with depends upon the
force law you use for the repulsion, but it won't be a regular
polyhedron, and it certainly won't be equidistant.
|
|
|
|
| Re: equally spaced points on a hypersphere? [message #41540 is a reply to message #41449] |
Fri, 29 October 2004 09:40 |
Craig Markwardt
Messages: 1869
Registered: November 1996
|
Senior Member |
|
|
Matt Feinstein <nospam@here.com> writes:
>
> I think that if 'equidistant' means that each point has the same
> relation to -every- neighboring point, then it implies that the points
> lie on a regular polyhedron.
Hmm, but consider a soccer ball (truncated icosahedron). The faces
are not all regular, and yet the nearest neighbors are all
equidistant, no?
> In any case, a lowest energy
> configuration may only be a local minimum with respect to small
> variations of the positions of the points, so the global properties of
> such a minimum are not necessarily unique.
I think if one uses a 1/r^2 potential, then there is a single global
minimum. I guess it's possible for the iterator program to get stuck
elsewhere.
Craig
--
------------------------------------------------------------ --------------
Craig B. Markwardt, Ph.D. EMAIL: craigmnet@REMOVEcow.physics.wisc.edu
Astrophysics, IDL, Finance, Derivatives | Remove "net" for better response
------------------------------------------------------------ --------------
|
|
|
|
| Re: equally spaced points on a hypersphere? [message #41541 is a reply to message #41449] |
Fri, 29 October 2004 09:10 |
tam
Messages: 48
Registered: February 2000
|
Member |
|
|
Craig Markwardt wrote:
> Matt Feinstein <nospam@here.com> writes:
>
>> On 29 Oct 2004 07:51:58 -0700, robert.dimeo@nist.gov (Rob Dimeo)
>> wrote:
>>
>>
>>> Hi,
>>>
>>> I would like to create (n+1) equidistant points on an n-dimensional
>>> sphere. The initial information provided is the center of the sphere,
>>> the radius, and *any* point on the sphere. From that you need to find
>>> the coordinates for the remaining n points. As a simple example,
>>> three equidistant points on a 2-dimensional sphere (a circle), can be
>>> located 120 degrees apart. Any hints on how to do this in general for
>>> n-dimensions?
>
>
> This is commonly called "tesselating" the sphere, or hypersphere in
> this case.
>
>
>> Unfortunately, when you go to dimension greater than two, there are
>> constraints on the number of 'equidistant' points you can have on a
>> sphere. For example, in 3-D, there are (only) five regular polyhedra,
>> so n can only have the values 4, 6, 8, 12, and 20 for a tetrahedron,
>> octahedron, cube, icosahedron, and dodecahedron.
>
>
> So is there any requirement that the tesselation produce a regular
> polyhedron?
>
> Clearly it is possible to place *any* number of equidistant points on
> a sphere via an iterative approach. As discussed on line, start
> with random placement of points, allow the points to repel each other,
> iterate until you reach the lowest energy configure.
>
> Whether such an approach will work for Rob, I don't know.
>
> Craig
>
I'm not sure what it means to have 'equidistant' points on a sphere.
I don't think the OP wants each point to be equidistant from all
other points -- I don't think that's possible for more than n+1 points
in an n-dimensional space.
Craig indicates one take on the problem, but the OP may want to
frame it more carefully, e.g., a different criterion might
be to maximize the mininum distance between any two points.
I don't know if that has the same solution. Matt points out
that only in a special cases will the soution be regular, for
most sets of points the 'facets' defined by points will not
all regular, equal polygons.
A quick Google search came up with
http://nrich.maths.org/askedNRICH/edited/1125.html
that gives some interesting references.
Regards,
Tom McGlynn
|
|
|
|
| Re: equally spaced points on a hypersphere? [message #41542 is a reply to message #41449] |
Fri, 29 October 2004 08:53 |
Matt Feinstein
Messages: 33
Registered: July 2002
|
Member |
|
|
On 29 Oct 2004 10:29:31 -0500, Craig Markwardt
<craigmnet@REMOVEcow.physics.wisc.edu> wrote:
> So is there any requirement that the tesselation produce a regular
> polyhedron?
>
> Clearly it is possible to place *any* number of equidistant points on
> a sphere via an iterative approach. As discussed on line, start
> with random placement of points, allow the points to repel each other,
> iterate until you reach the lowest energy configure.
>
I think that if 'equidistant' means that each point has the same
relation to -every- neighboring point, then it implies that the points
lie on a regular polyhedron. In any case, a lowest energy
configuration may only be a local minimum with respect to small
variations of the positions of the points, so the global properties of
such a minimum are not necessarily unique.
Matt Feinstein
--
There is no virtue in believing something that can be proved to be true.
|
|
|
|
| Re: equally spaced points on a hypersphere? [message #41543 is a reply to message #41449] |
Fri, 29 October 2004 08:29 |
Craig Markwardt
Messages: 1869
Registered: November 1996
|
Senior Member |
|
|
Matt Feinstein <nospam@here.com> writes:
> On 29 Oct 2004 07:51:58 -0700, robert.dimeo@nist.gov (Rob Dimeo)
> wrote:
>
>> Hi,
>>
>> I would like to create (n+1) equidistant points on an n-dimensional
>> sphere. The initial information provided is the center of the sphere,
>> the radius, and *any* point on the sphere. From that you need to find
>> the coordinates for the remaining n points. As a simple example,
>> three equidistant points on a 2-dimensional sphere (a circle), can be
>> located 120 degrees apart. Any hints on how to do this in general for
>> n-dimensions?
This is commonly called "tesselating" the sphere, or hypersphere in
this case.
> Unfortunately, when you go to dimension greater than two, there are
> constraints on the number of 'equidistant' points you can have on a
> sphere. For example, in 3-D, there are (only) five regular polyhedra,
> so n can only have the values 4, 6, 8, 12, and 20 for a tetrahedron,
> octahedron, cube, icosahedron, and dodecahedron.
So is there any requirement that the tesselation produce a regular
polyhedron?
Clearly it is possible to place *any* number of equidistant points on
a sphere via an iterative approach. As discussed on line, start
with random placement of points, allow the points to repel each other,
iterate until you reach the lowest energy configure.
Whether such an approach will work for Rob, I don't know.
Craig
--
------------------------------------------------------------ --------------
Craig B. Markwardt, Ph.D. EMAIL: craigmnet@REMOVEcow.physics.wisc.edu
Astrophysics, IDL, Finance, Derivatives | Remove "net" for better response
------------------------------------------------------------ --------------
|
|
|
|
| Re: equally spaced points on a hypersphere? [message #41546 is a reply to message #41449] |
Fri, 29 October 2004 08:16 |
Matt Feinstein
Messages: 33
Registered: July 2002
|
Member |
|
|
On 29 Oct 2004 07:51:58 -0700, robert.dimeo@nist.gov (Rob Dimeo)
wrote:
> Hi,
>
> I would like to create (n+1) equidistant points on an n-dimensional
> sphere. The initial information provided is the center of the sphere,
> the radius, and *any* point on the sphere. From that you need to find
> the coordinates for the remaining n points. As a simple example,
> three equidistant points on a 2-dimensional sphere (a circle), can be
> located 120 degrees apart. Any hints on how to do this in general for
> n-dimensions?
Unfortunately, when you go to dimension greater than two, there are
constraints on the number of 'equidistant' points you can have on a
sphere. For example, in 3-D, there are (only) five regular polyhedra,
so n can only have the values 4, 6, 8, 12, and 20 for a tetrahedron,
octahedron, cube, icosahedron, and dodecahedron.
Matt Feinstein
--
There is no virtue in believing something that can be proved to be true.
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
