NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/sci/math/17459

Text File | 1992-12-28 | 14.5 KB | 364 lines

Newsgroups: sci.math
Path: sparky!uunet!munnari.oz.au!spool.mu.edu!agate!usenet.ins.cwru.edu!eagle!convx1.lerc.nasa.gov!sshws
From: [e-mail] (Herb Schilling)
Subject: SUMMARY: Equispaced points on sphere?
Message-ID: <[e-mail]>
Sender: [e-mail]
Nntp-Posting-Host: convx1.lerc.nasa.gov
Organization: NASA Lewis Research Center
Date: Mon, 28 Dec 1992 16:11:33 GMT
Lines: 352


After a long delay ( sorry ) , here is a summary of replies to my question
on how do you place N points on a 3-D sphere such that the minimum
distance between any two points is a maximum.

============================================================================

Received: from enet-gw.pa.dec.com by convx1.lerc.nasa.gov (5.64/10.0)   id
AA06832; Tue, 1 Dec 92 09:21:06 -0500
Received: by enet-gw.pa.dec.com; id AA01781; Tue, 1 Dec 92 06:20:58 -0800
Message-Id: <[e-mail]>
Received: from 3d.enet; by decwrl.enet; Tue, 1 Dec 92 06:20:59 PST
Date: Tue, 1 Dec 92 06:20:59 PST
From: Jim Roth MLO1-2/U2 223-6562 Workstations Software  01-Dec-1992 0923
<[e-mail]>
To: [e-mail]
Apparently-To: [e-mail]
Subject: Re: Equispaced points on sphere? ( Repeat?)

In article <[e-mail]>, you write...
>
>I apologize if this was just discussed ( I think it was ), but I
>am trying to figure out how to determine the locations of n equispaced
>points on the surface of 3-D sphere.

As far as I know, such equidistant points only exist for cases coming
from the classcial polyhedra (squares, cubes, octahedra, icosahedron...)

You can get a close approximation using geodesic dome techniques for some
values of N though.

Start with a parent polyhedron like an icosahedron and triangulate the
faces into more equilateral triangles.  Projecting the points on the sphere
will not have too bad a discrepancy.

For general N I don't know of a simple way to do this, or if it's even
possible without being related to geodesic domes.

- Jim

============================================================================

Received: from vnet.ibm.com by convx1.lerc.nasa.gov (5.64/10.0) id AA29744;
Tue, 1 Dec 92 10:58:06 -0500
Message-Id: <[e-mail]>
Received: from PKMFGVM1 by vnet.ibm.com (IBM VM SMTP V2R2) with BSMTP id
8863; Tue, 01 Dec 92 10:55:21 EST
Date: Tue, 1 Dec 92 10:52:48 EST
From: "Phil Hanna" <[e-mail]>
To: [e-mail]
Subject: Equispaced points on a sphere

Herb, this is an unsolved problem I have been interested in for years.
Are you sure you are describing exactly what you want?  Do you mean
equidistant or maximally distant?  For example, for n=5, you can
locate four points equidistant around the equator and one point at
the north pole, and if you think of these points as vertices of a
square pyramid, all of the edges are the same length.  But all five
points are not equidistant from each other (consider the diagonals
of the base).  If you are thinking of "equidistant" in terms of
some definition of "neighboring points", this is not the solution.
If you think of circular caps extending out from each point and
try to maximize the common radius, it turns out that a better solution
is north pole/south pole/three points at 120 degrees along the
equator.  I conjecture that for sufficiently large n, the solution
is not unique.

I have found some references in the literature.  Martin Gardner
devoted one of his columns in Scientific American (I think it was
in mid to late 1969) to this problem.  He cast it in terms of
how to locate n lunar bases as far apart from each other as possible.
There is a more rigorous treatment in the book "Regular Figures"
by Fejes-Toth.  It turns out that the problem occurs in nature, in
the optimum placement of dimples on a pollen grain.

As of 1969, there were solutions for specific values of n up to
about 13 but no general solution.  It is a rich problem; think
of solutions in terms of the polyhedra that they determine.  What
do these polyhedra have in common?  Of the five platonic solids,
you would think they all are solutions for n equal to their
number of vertices, but this is only true for four of them.  The
cube is not the solution for n=8; a 45 degree twisted cube is.

Please let me know what you find out on this problem.  In particular,
see if you can come up with a good definition, where "good" means
that it produces solutions that intuitively look right.  Thanks.

Phil Hanna
[e-mail]


============================================================================

Received: from newton.visgraf.impa.br by convx1.lerc.nasa.gov (5.64/10.0)
    id AA05914; Tue, 1 Dec 92 13:33:51 -0500
Received: from Phong (phong.visgraf.impa.br) by Newton.visgraf.impa.br
(4.1/SMI-4.1)    id AA10235; Tue, 1 Dec 92 16:28:13 EDT
Date: Tue, 1 Dec 92 16:28:12 EDT
From: [e-mail] (Luiz Henrique de Figueiredo)
Message-Id: <[e-mail]>
To: [e-mail]
Subject: Re: Equispaced points on sphere?

If you can settle for *almost* equispaced points, then a simple algorithm is:
        1. start with a icosaheadron
        2. foreach triangle
                - divide triangle into 4, by connecting midpoints of sides
        3. repeat step 2 as much as neeeded.

I can send you code for that if you need.
--
Luiz Henrique de Figueiredo                        email: [e-mail]
IMPA-Instituto de Matematica Pura e Aplicada              [e-mail]
Estrada Dona Castorina 110                         voice: [phone] x226
22460 Rio de Janeiro, RJ, Brasil                     fax: [phone]
--

============================================================================
============

Received: from kruuna.Helsinki.FI by convx1.lerc.nasa.gov (5.64/10.0)   id
AA27248; Wed, 2 Dec 92 09:10:06 -0500
Received: from klaava.Helsinki.FI by kruuna.helsinki.fi with SMTP id
AA07270 (5.65c8/IDA-1.4.4 for <[e-mail]>); Wed, 2 Dec
1992 16:09:57 +0200
Received: by klaava.Helsinki.FI (4.1/SMI-4.1)   id AA28515; Wed, 2 Dec 92
16:09:57 +0200
Date: Wed, 2 Dec 92 16:09:57 +0200
From: [e-mail] (Taneli Huuskonen)
Message-Id: <[e-mail]>
To: [e-mail]
Subject: Re: Equispaced points on sphere? ( Repeat?)
Newsgroups: sci.math
References: <[e-mail]>

In sci.math you write:


>I apologize if this was just discussed ( I think it was ), but I
>am trying to figure out how to determine the locations of n equispaced
>points on the surface of 3-D sphere.

Depends on how you define "equispaced".  The most natural definition,
IMHO, would be to require that the points be the corners of a regular
polyhedron, but there are just five regular polyhedra, corresponding to
n=4, 6, 8, 12, and 20.  Of course, you can arrange the points at the
corners of a regular n-sided polygon lying on a great circle (or even a
small circle) of the sphere, which would make them "equidistant" in a
fairly natural sense, but I don't find that quite satisfying.  There are
other possibilities as well, but I suspect things may get somewhat
complicated when you explore them.
--
Taneli Huuskonen |   finger [e-mail]   | Garanteely speling
-----------------|-------------------------------------| & grammer errur free
 Did I claim | S e va'gy tala'n me'g jobban boldogi't  |---------------------
 something?  | Mint ha ott volne'k, ahol lenni va'gyok.  -Peto"fi Sa'ndor

============================================================================



Article 26715 of sci.math:
Newsgroups: sci.math
Path: eagle!usenet.ins.cwru.edu!wsu-cs!trace.eng.wayne.edu!uds
From: [e-mail] (Seetamraju Udaybhaskar)
Subject: Re: Equispaced points on sphere? ( Repeat?)
Message-ID: <[e-mail]>
Sender: [e-mail] (Usenet News)
Reply-To: [e-mail] (Seetamraju Udaybhaskar)
Organization: Wayne State University, Detroit
References: <[e-mail]>
Date: Wed, 2 Dec 1992 01:26:01 GMT
Lines: 65

In article [e-mail] (Herb Schilling) writes:
>
>am trying to figure out how to determine the locations of n equispaced
>points on the surface of 3-D sphere.


I have a algorithmic solution.

The idea is based on this observation.  ANy 3 neighboring points will
form a `triangle' (in quotes, because U dont have a straight line
triangle on a sphere, but I hope U get what I am seeing in my mind.
maybe we shall call it a `bulged triangle' made up of arcs...)

Now since all points are equidistant, clearly this bulged triangle
will be `equilateral' and more importantly, all such triangles are
identical.

Hence if there are n equidistant points on the sphere, there are c(n,3)
such triangles.

Clearly,  if f(l) is the area of each bulged triangle (all are equal in
area), then

                f(l) * c(n,3)  == 4.pi.r^2              ---- (1)

where l is the `equi'-distance between the equidistant points.

Now heres the fuzzy part...  I am giving a not so clear derivation of
f(l)... then since eqn-(1) contains only one variable (i.e., the distance
`l') one can solve for it...!!

After I solve for `l', I use a compass or divider (in software ofcourse)
to `mark-out' all the neighboring points of ANY ARBITRARY INTIAL point
and THEN the NEIGHBORING points of THOSE NEIGHBORING points  and so on...


Well, here's the formula for f(l) ::::

Clearly, each such triangle is HALF the area of a `bulged-square' whose
sides are of length `l'.  The area of the square (I am guessing here!!)

                  (theta)^2
                = _______  * 4 * pi * r^2               ---- (2)
                   (360)^2

where theta is the angle subtended by the arc connecting ANY TWO neighboring
equidistant points.  right ?

Clearly, theta = l / 2pi*r  in radians :: to be converted into degrees...


Hence f(l) =     (l)^2 *  4 * pi * r    * a conversion factor for
radians-to-degrees
                --------------------
                2 * (360)^2 *  2 * pi * r

          =   l^2 / (2 * pi)^2     =   ( l / 2*pi)^2.


This is too simple a formula.   I am not at all confident of it...
But, if U can correctly determine f(l), the problem is solved...


Seetamraju Udaya Bhaskar Sarma
(email : seetam @ ece7 . eng . wayne . edu)




============================================================================



Received: from spam.maths.adelaide.edu.au by convx1.lerc.nasa.gov
(5.64/10.0)   id AA15760; Wed, 2 Dec 92 20:57:51 -0500
Received: by spam.maths.adelaide.edu.au (5.61+IDA+MU/UA-5.21)   id AA23545;
Thu, 3 Dec 1992 12:08:51 +1030
Date: Thu, 3 Dec 1992 12:08:51 +1030
From: Mark A Stewart <[e-mail]>
Message-Id: <[e-mail]>
To: [e-mail]
Subject: Re: Equispaced points on sphere? ( Repeat?)
Newsgroups: sci.math
In-Reply-To: <[e-mail]>
Organization: Statistics, Pure & Applied Mathematics, University of Adelaide

Gooday,
        This is just a top of the head response so dont take it as gospel.
But I believe the way to do this is to look at the symetry groups of the
plutonic solids and then look at the finite fixed point sets of these groups.
These points correspond to either vertices, midpoints of the edges, and
midpoints
of the faces all of which may be scaled to fit on the sphere and satisfy your
condition. Of course this somewhat restricts the choices of 'n'.
        If this doesnt help mail me, as I looked at a similar problem for
a geographer some years back now and have the notes stashed away somewhere.

        Mark Stewart

============================================================================


Received: from mummy.agsm.unsw.OZ.AU by convx1.lerc.nasa.gov (5.64/10.0)
    id AA18104; Thu, 3 Dec 92 01:18:01 -0500
Received: by mummy.agsm.unsw.OZ.AU id AA07927 (5.65c/IDA-1.4.4 for
[e-mail]); Thu, 3 Dec 1992 17:19:59 +1100
Date: Thu, 3 Dec 1992 17:19:59 +1100
From: Glen Barnett <[e-mail]>
Message-Id: <[e-mail]>
To: [e-mail]
Subject: Re: Equispaced points on sphere? ( Repeat?)
Newsgroups: sci.math
In-Reply-To: <[e-mail]>
Organization: The Australian Graduate School of Management
Cc:

In article <[e-mail]> you write:
>
>I apologize if this was just discussed ( I think it was ), but I
>am trying to figure out how to determine the locations of n equispaced
>points on the surface of 3-D sphere.

There was a fair discussion of this fairly recently. Strictly, I guess,
only 1,2,3 and 4 points can be placed so all points are equally
distant from all other points (and the placements are obvious).

What you probably refer to would correspond (for >3 points) to
the vertices of an inscribed Platonic solid - i.e. 4,6,8,12,20
points can be placed 'equidistant' in the same sense that an inscribed
regular hexagon places 6 points 'equidistantly' when inscribed in a circle -
they aren't equidistant, except from their closest neighbours.

The interesting questions come when you try to place, say 5
points "as far apart as possible" on a sphere. In general, I don't
think there is an algorithm for this.

>
> By the way, I searched hi and low for archives of this newsgroup but
>was unable to find one. Is there one ?
>
If its not in the FAQ (posted to sci.math regularly), I doubt it.

Glen


==============================================================================


Received: from liberty.uc.wlu.edu by convx1.lerc.nasa.gov (5.64/10.0)   id
AA01465; Thu, 3 Dec 92 14:29:58 -0500
Message-Id: <[e-mail]>
Received: by liberty.uc.wlu.edu (16.8/16.2) id AA16847; Thu, 3 Dec 92
14:29:26 -0500
Date: Thu, 3 Dec 92 14:29:26 -0500
From: Tim Murdoch <[e-mail]>
To: [e-mail]

To: [e-mail] (Herb Schilling)
Subject: Re: Equispaced points on sphere? ( Repeat?)
Newsgroups: sci.math
Organization: Washington & Lee University

Hi,

I'm responding to your post about equi-spaced points on a sphere. Do you
mean a set of points such that any pair of points are the same distance
apart? Also, are you talking about a three dimensional sphere or a sphere
in ordinary 3-space? I can answer your question if your answer to my first
question is yes. In fact, I have a paper to appear in the American
Mathematical Monthly that addresses this very question.

I look forward to your reply.

-- <<Tim Murdoch>>

--
Herb Schilling , NASA Lewis Research Center , 21000 Brookpark Road, MS 142-5
Cleveland, Ohio 44135 . [phone]       [e-mail]