home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 18008 < prev    next >
Encoding:
Text File  |  1993-01-11  |  3.8 KB  |  96 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cs.utexas.edu!zaphod.mps.ohio-state.edu!moe.ksu.ksu.edu!ux1.cso.uiuc.edu!news.cso.uiuc.edu!needham
  3. From: needham@symcom.math.uiuc.edu (James Needham)
  4. Subject: Re: Points on Sphere
  5. References: <1993Jan11.184545.18912@pinet.aip.org> <1istp4INNfgj@matt.ksu.ksu.edu>
  6. Message-ID: <C0pwtn.LyF@news.cso.uiuc.edu>
  7. Sender: usenet@news.cso.uiuc.edu (Net Noise owner)
  8. Organization: University of Illinois at Urbana
  9. Date: Tue, 12 Jan 1993 01:44:09 GMT
  10. Lines: 84
  11.  
  12. Since there seems to be interest in placing n points on a 
  13. sphere, I thought that I would post what little I know.  I 
  14. know that I've been working on the problem for a year, 
  15. and it has stubbornly resisted every means of attack. 
  16.  
  17. The generalized problem is this:  place n points on the 
  18. unit sphere in order to extremize Sum(i<j, d(p(i), p(j)) ** 
  19. alpha), where d is the Euclidean distance.  For alpha > 0, 
  20. we want to maximize the sum, for alpha < 0, we want to 
  21. minimize the sum.  alpha = -.5 corresponds to the 
  22. potential energy determined by n point charges.  I've 
  23. been concentrating on alpha = 1.
  24.  
  25. The corresponding problem in the plane, putting points 
  26. on the circle, has been solved for many values of alpha.  
  27. See (1) and (2).  Suffice it to say that the regular n-gon 
  28. usually works; but for 1 < alpha < 2, I think the problem 
  29. is still open.
  30.  
  31. For the sphere, tough, most of the interesting cases are 
  32. still unknown.  There is an algorithm (see (3)) that takes 
  33. n given points and moves them around (basically 
  34. LaGrange multipliers) to what *seems* to be the best 
  35. possible configurations.  Unfortunately, for alpha = 1, the 
  36. optimal configuration can only be *proved* for n = 3 
  37. (equilateral triangle), n = 4 (regular tetrahedron), n = 12 
  38. (regular whatever), and n = 24 (regular whatever).  The 
  39. algorithm indicates that the following are optimal:
  40.  
  41. n = 5:  bipyramid
  42. n = 6:  bipyramid
  43. n = 7:  one north pole and three pairs symmetric through 
  44. the z axis
  45. n = 8:  skewed cube
  46. n = 9:  equilateral triangle on the equator with skewed 
  47. equilateral triangles        
  48. above and below it
  49.  
  50. I have "optimal" solutions for n through about 50.  Again, 
  51. hardly any of these can be proven.  The hope that there 
  52. is one method that will take in n and spit out the best 
  53. configuration is fading.  The placement really seems to 
  54. depend on the particular properties of n.  At one point I 
  55. even had a conjecture relating it to twin primes.
  56.  
  57. The problem with this algorithm is that it behaves 
  58. somewhat chaotically.  It is possible that an initial 
  59. configuration gets sucked into a *local* extremal 
  60. configuration (for example, with 5 points one can start 
  61. with configurations that converge to the pyramid rather 
  62. than the optimal bipyramid).  This seems to happen, 
  63. though, with probability 0.  Does anybody out there know 
  64. anything about chaotic dynamical systems on higher 
  65. dimensional manifolds? If so, you might find this 
  66. problem interesting.
  67.  
  68. One might also suspect that the optimal configurations 
  69. remain the same as one varies alpha.  This is not the case.  
  70. With seven points , the bipyramid is minimal for alpha = 
  71. -.5, while for alpha = 1 the configuration described above 
  72. is better.  (I think that the strange configuration 
  73. described above for 7 points gives way to the bipyramid 
  74. at about alpha = .6, if I remember correctly.)
  75.  
  76. There are lots of interesting problems in here, but don't 
  77. get obsessed with it.  Any questions or comments will be 
  78. cheerfully entertained!
  79.  
  80. 1.  R. Alexander and K. Stolarsky, Extremal problems of 
  81. distance geometry related to energy integrals, Trans. of 
  82. AMS 193 (1974).
  83.  
  84. 2.  G. Bjorck, Distributions of positive mass which 
  85. maximize a certain generalized energy integral, Ark. Mat. 
  86. 3 (1956), 255-269.
  87.  
  88. 3.  J. Berman and K. Hanes, Optimizing the arrangement of 
  89. points on the unit sphere, Math. Comp. 31 (1977), 1006-
  90. 1008.
  91.  
  92.  
  93. Jim Needham
  94. needham@symcom.math.uiuc.edu
  95.  
  96.