Conference rusure::math

Yes.

================================================================================
  SPHINX::PATTERSON            Mathematics at DEC             7-JAN-1985 08:43  
  Note #206            -{ A rose by any other name... }-          No responses  
--------------------------------------------------------------------------------

remarkable, this is isomorphic to a problem that has plagued me for a bit.

I had considered marbles of 'small' diameter and equally repulsive forces
constrained to be within a 'large' diameter basketball (ok I like sports).

the platonic solids are formed by the appropriate number of marble-vertices,
but like the author of the first note what of 5 points?? I'm sure his
suspicion, (same as mine), is good - but I lack a proof.  I was considering
a maximization problem with Lagrangian multipliers and so forth, but this
*does* seem inelegeant.

Other cases I'm certain form archimedean solids, again- proof by suspicion.

An aside, a dual can be obtained by considering attractive forces and
the marbles constrained to be on the outside of the sphere.  If one
considers 'many' marbles to initially and attractive forces *decreasing*
with *decreasing* proximity, what polytope is formed??

oops the 'to' 2 sentences above is superflous.

thanks
carl

For five repulsive 'bugs', ...

If it's assumed that two bugs wander to opposite poles, then the 'obvious'
solution is, indeed, correct (and fairly obviously, too).

If no two bugs are at opposite poles, it should be possible to point out a
contradiction, by a transformation that decreases the total repulsiveness
between the bugs (consider, for example, the two bugs that are furthest apart).
This part will likely depend on the 'function' to describe the repulsiveness as
a function of the separating distance.

The optimum for five bugs is reached when they are at the corners of the 
imbedded regular octahedron. In this position they are all at C/4 (C is the 
circumference) from the nearest neighbor. It is interesting that any one of
them that is adjacent to the unoccupied corner of the octahedron can move
to that corner, all the while leaving the distances constant. Also any two
of the bugs can exchange positions (possibly with the cooperation of a
third bug) without changing the C/4 distance. Adding a sixth bug at the
unoccupied corner fills out the pattern. 

The first REALLY interesting case occurs with 7 bugs. One near-optimal
situation has two bugs at poles with the other 5 around the equator. The
polar bugs are at distance C/4, while the equatorial bugs are at C/5, from
their neighbors. Clearly there is some room to wiggle the equatorial bugs
North and South to increase their distance to something between C/4 and C/5. 

Another configuration has one bug at the North pole, three bugs just above 
the equator, and three below the equator. Again, the distances are 
somewhere between C/4 and C/5, but what are they?

This is fairly interesting problem which probably has to be attacked by
relaxation techniques. Anybody got any useful programs squirreled away?

Lynn -
	I believe you're mistaken.  It's very doubtful that the
	configuration you mention for five bugs is truly optimum.

					- Gilbert

Assume the minimum distance is d > C/4. Then for each bug, the other 4 bugs
must all reside on the opposite hemisphere, beyond the 'equator' defined
by the first bug as a pole. The sum of the great-circle distances among those 
4 is dominated by the circumference of a circle which lies between them and
the equator, which in turn is less than the length C of the equator. So 4*d
< C, and d< C/4, which is a contradiction. So the minimum distance must be
exactly C/4. - Lynn Yarbrough

To bring this up again, can anyone complete this table for this guy?

P.S.  re .4, .6:  For 5, the arrangement where the 3 "bugs" on the equator are
3 points on an equilateral triangle are more distant from each other than if
they occupied 3 of the 4 corners of a square.  In either configuration, the
distance from the poles remains constant, so the solution reduces to placing 3
bugs on a circle so they are equidistant, which is an equilateral triangle
whose vertices are on the circle.

Newsgroups: net.math
Path: decwrl!pyramid!ncr-sd!randall
Subject: Equal Spaced Points on the Sphere
Posted: 29 Aug 86 18:56:07 GMT
Organization: NCR Corporation, San Diego
References:
Keywords:Points on a Sphere
 
Alright, I'll try again, after the tremendous response from my last question.
Does anyone know the answer, or how to find the answer to the following
question:
	 What are the positions of n-points on the unit sphere,
	 such that the sum of their mutual distances is a maximum?
 
I do know the following:
 
	 N             Arrangement of points
 
	 1             any point on sphere
	 2             any line thru center of sphere (diameter)
	 3             any equilateral triangle, vertices on sphere
	 4             any regular tetrahedron, vertices on sphere
	 5             ?
	 6             any regular octahedron, vertices on sphere
	 7             ?
	 8             any hexahedron(cube), vertices on sphere
	 9             ?
	 10-           ??
 
In particular does anyone know the answer for 5 equidistant or maximally spaced
points on the unit sphere? What about 7 or 9 and up? I haven't mentioned the
dodecagon or the isocahedron, as the 5 regular Platonic solids would furnish
answers to some the the spacings, or are there other figures that would work
just as well also, for n=4,6 or 8? Let me know what you all out there think.
Thanks, - Randall

Newsgroups: net.math
Path: decwrl!nsc!csi!epimass!jbuck
Subject: Re: Equal Spaced Points on the Sphere
Posted: 30 Aug 86 01:23:59 GMT
Organization: Entropic Processing, Inc., Cupertino, CA
Keywords: Points on a Sphere
 
In article <[email protected]> [email protected] (0000-Randall Rathbun) writes:
>Alright, I'll try again, after the tremendous response from my last question.
>Does anyone know the answer, or how to find the answer to the following
>question:
>	 What are the positions of n-points on the unit sphere,
>	 such that the sum of their mutual distances is a maximum?
>
>I do know the following:
>
>	 N             Arrangement of points
>...
>	 8             any hexahedron(cube), vertices on sphere
 
Wrong.  The solution for eight points consists of two squares in
separate and parallel planes, with one square rotated 45 degrees
relative to the other square.
 
 
-- 
- Joe Buck 	{ihnp4!pesnta,oliveb,nsc!csi}!epimass!jbuck
  Entropic Processing, Inc., Cupertino, California

    The answer for "3" is wrong, it's not "any equilateral triangle".
    Only ones whose vertices are on a "great circle" will do.
    
    /Eric

    What are we max/minimizing here?  The original problem asks where
    the bugs would wander to.  Do the bugs:
    
    maximize the sum of all mutual distances?
  
    	SOAMD =  0.5  SUM (   SUM  ( DIST (Pi, Pj) ) )
                     i=1,n  j=i+1,n
   
    maximize the minimum distance?
                                 
    	MD =  MIN  (   MIN   ( DIST (Pi, Pj) ) )
             i=1,n   j=i+1,n
   
    minimize the stored energy of the system, assuming that all
    bugs have the same charge?
                                               2
    	PE =  SUM (   SUM   ( 1 / DIST (Pi, Pj)  ) )
             i=1,n  j=i+1,n
                       
    The solution to the PE problem for n=5 is three points in an
    equilateral triange on the equator and two points at the poles.
    This is the arrangement of electron orbitals in a valence 5 atom
    (or maybe it was valence 7 -- my chemistry is rusty).  I would have
    to think more about the other two.
    
    Are any of these three optimization criteria equivalent?
    
    john

Article 27384 of sci.math
Path: ryn.mro4.dec.com!nntpd.lkg.dec.com!news.crl.dec.com!deccrl!caen!spool.mu.edu!uunet!mcsun!uknet!cam-cl!cam-cl!cet1
From: [email protected] (C.E. Thompson)
Newsgroups: sci.math
Subject: Re: How does one tesselate a spherical surface?
Keywords: tesselate sphere triangle
Message-ID: <[email protected]>
Date: 19 Jun 92 21:55:59 GMT
Article-I.D.: cl.1992Jun19.215559.17737
References: <[email protected]> <[email protected]>
Sender: [email protected] (The news facility)
Reply-To: [email protected] (C.E. Thompson)
Organization: U of Cambridge Computer Lab, UK
Lines: 57

In article <[email protected]>, [email protected]
(Mark Fulk) writes:
|> In article <[email protected]> [email protected]
|> (Darrell Roy Hougen) writes:
|> >I am wondering ...  is it possible to find a set of points on the
|> >surface of a sphere such that all the points lie at the corners of
|> >equilateral triangles of equal size?  Is it possible to do this for
|> >any number of points greater than to four?  How is it done for N
|> >points?  If it can't be done for every N, is there some N greater than
|> >four for which it works?  Are there an infinite number of such N's?
|> 
|> The possible ways are:
|> 
|> 4 points: vertices of a tetrahedron
|> 6 points: vertices of an octahedron
|> 12 points: vertices of an icosahedron
|> 
|> These are the only ways, as any such placement generates a regular
polyhedron,
|> of which there are five: the above, the cube, and the dodecahedron.
|> 
|> >The real problem that I am trying to solve is the problem of evenly
|> >distributing N points on the surface of a sphere.  Right now I am
|> >using a rather ad hoc method that usually gives reasonable results but
|> >sometimes yields a pair of points that are unusually close together or
|> >far apart.  Using triangles appears to be one way of ensuring that the
|> >points are evenly distributed.
|> 
|> You might look up geodesic dome designs.

There are rather a lot of ways in which one might try to make "evenly
distributed" precise, which lead to different problems none of which
have complete known solutions. [1] section F17 gives some references
for the following variants:

  Maximise the minimum pairwise distance between points of the set
   (Tammes' problem, probably best known of all the variants).
  Minimise the maximum distance of any point of the sphere from a
   point of the set.
  Minimise the arithmetic mean (or alternatively, the sum of squares)
   of the n(n-1)/2 distances between points of the set.
  Minimise the potential energy of N equal charges placed at the points
   of the set.
  Maximise the volume of convex hull of the N points.
  Minimise the volume of the polyhedron formed by the tangent planes
   to the sphere at the N points.

In the first two cases it isn't too difficult to show that if a regular
polyhedron with triangular faces exists (N=4, 6, or 12) then it provides
the optimal solution, but even this isn't known to be true for the others.

[1] H.T.Croft, K.J.Falconer, R.K.Guy, "Unsolved Problems In Geometry",
    Springer-Verlag (1991) ISBN 0-387-97506-3

Chris Thompson
JANET:    [email protected]
Internet: [email protected]


Article 27561 of sci.math
Path: ryn.mro4.dec.com!nntpd.lkg.dec.com!news.crl.dec.com!deccrl!decwrl!olivea!uunet!mcsun!uknet!cam-cl!cam-cl!cet1
From: [email protected] (C.E. Thompson)
Newsgroups: sci.math
Subject: Maximising the r.m.s. separation of points on a sphere is easy
Keywords: sphere
Message-ID: <[email protected]>
Date: 25 Jun 92 13:46:12 GMT
References: <[email protected]>
Sender: [email protected] (The news facility)
Reply-To: [email protected] (C.E. Thompson)
Organization: U of Cambridge Computer Lab, UK
Lines: 44

In article <[email protected]>, I wrote, w.r.t. arranging
n points on a sphere:
|> 
|> There are rather a lot of ways in which one might try to make "evenly
|> distributed" precise, which lead to different problems none of which
|> have complete known solutions. [1] section F17 gives some references
|> for the following variants:
...  
|>   Minimise the arithmetic mean (or alternatively, the sum of squares)
|>    of the n(n-1)/2 distances between points of the set.

First: I meant "maximise", of course. Minimising is really easy...

Second: The sum of squares case turns out to be rather trivial. [1] F17(4)
refers to it only in a throw-away remark "We can also ask to maximise the
sum of the squares of the distances".

Let v_i, 1<=i<=n be the vectors from the centre to n points on the unit
sphere. Then the sum involved is

      {\sum\sum}_{i<j} (v_i - v_j)^2
    = (1/2) \sum_{i=1}^{n} \sum_{j=1}^{n} v_i^2 - 2 (v_i.v_j) + v_j^2 
    = n^2 - (\sum_{i=1}^{n} v_i)^2

which is maximised by making \sum(v_i) = 0, i.e. when the centroid 
of the n points lies at the centre of the sphere. (Clearly this is
possible provided n>1.)

When n>=4 there are infinitely many non-congruent arrangements that
achieve the maximum value. For n even, one of these is to have two
sets of n/2 points each coincident at opposite ends of a diameter.
So this wouldn't be a good way to achieve Darrall Hougen's original
requirement of "evenly distributing" the points: the measure has
given too much weight to getting points as far apart as possible.

 
[1] H.T.Croft, K.J.Falconer, R.K.Guy, "Unsolved Problems In Geometry",
    Springer-Verlag (1991) ISBN 0-387-97506-3


Chris Thompson
Cambridge University Computing Service
JANET:    [email protected]
Internet: [email protected]