31
$\begingroup$

I am looking for an algorithm to put $n$-points on a sphere, so that the minimum distance between any two points is as large as possible.

I have found some related questions on stackoverflow but those algorithms are not an exact solution more random distributions. For special number of points (inscribed Platonic solids) it is clear but how about 5 points for example. I would be grateful for hints to the literature.

Thank you everyone for your time.

$\endgroup$
  • 16
    $\begingroup$ This problem is unsolved for large number of points. $\endgroup$ – Alexandre Eremenko Jul 29 '15 at 11:26
  • 10
    $\begingroup$ For a couple of related papers, see arXiv:math.MG/0611451 and arXiv:math/0607446. $\endgroup$ – Richard Stanley Jul 29 '15 at 11:59
  • 3
    $\begingroup$ 5 points is a strange case: the optimal distance is no better than it is for 6 (so an optimal arrangement can be gotten by taking the 6-point arrangement and deleting a point). See mathoverflow.net/questions/208484/…. $\endgroup$ – Will Brian Jul 30 '15 at 11:30
35
$\begingroup$

There is considerable literature on this question, and closely related variations. See:

  • The Thompson problem: Which configurations of $n$ electrons on a sphere minimize the electrostatic potential energy?
  • The Tammes problem: Which configurations of $n$ points on a sphere maximize the smallest distance between any two points? Sometimes phrased as packing $n$ congruent circles on a sphere:


          DiskPacking
          (Image from Paul Sutcliffe.)
According to

Musin, Oleg R., and Alexey S. Tarasov. "The Tammes problem for $N=14$." arXiv:1410.2536 Abstract (2014).

the Tammes problem is solved exactly for

  • For $n=3,4,6,12$ by L. Fejes Toth (1943).
  • For $n=5,7,8,9$ by Schütte and van der Waerden (1951).
  • For $n=10,11$ by Danzer (1963). Added (8Sep15): Exact radius for $n=10$ by Sugimoto & Tanemura.
  • For $n=24$ by Robinson (1961).
  • For $n=13, 14$ by Musin and Tarasov (2014).
              N=14.
              Fig.1 from Musin & Tarasov: $n=14$.
    Added (8Sep15): The exact radius for $n=10$ was just found:

Teruhisa Sugimoto, Masaharu Tanemura. "Exact value of Tammes problem for N=10." Sep 2015. arXiv 1509.01768 Abstract.


          STFig1b
          Fig.1b from Sugimoto & Tanemura.


Added (31Dec2017) in response to a question by @R_Berger: For $n=20$, the best arrangement for the Tammes problem is not the dodecahedron's vertices. The optimal is unknown, but this beats the dodecahedron:


          DodecaTammes
          Coordinates from Neil Sloane link, due to R.H. Hardin, N.J.A. Sloane & W.D. Smith (1994).


$\endgroup$
  • 7
    $\begingroup$ There is a problem similar to the Thompson problem, which is to find the minimum potential energy of a continuous charge distribution on a nonspherical conductor. There is a surprising set of exact solutions for some special shapes, in which the charge density is proportional to the fourth root of the absolute value of the Gaussian curvature. I W McAllister 1990 J. Phys. D: Appl. Phys. 23 359 doi:10.1088/0022-3727/23/3/016 $\endgroup$ – Ben Crowell Jul 29 '15 at 19:25
  • 2
    $\begingroup$ @BenCrowell: Nice! (McAllister, I. W. "Conductor curvature and surface charge density." Journal of Physics. D, Applied Physics 23.3 (1990): 359-362.) That anything interesting is the $4$-th root of the curvature is amazing. $\endgroup$ – Joseph O'Rourke Jul 29 '15 at 21:19
  • 2
    $\begingroup$ What's most surprising to me is that there is a link between a global property extrinsic to the surface (energy) and a local, intrinsic property (curvature). $\endgroup$ – Ben Crowell Jul 29 '15 at 23:11
  • 3
    $\begingroup$ $n=20$ is not a dodecahedron, why not and who solved that? $\endgroup$ – Rudi_Birnbaum Dec 31 '17 at 9:29
13
$\begingroup$

Since you are asking about an algorithmic perspective, I wanted to point out that a closely related variation (with logarithmic potential instead of hard core potential) is the subject of one of Smale's "Mathematical Problems for the Next Century." In Problem 7, Smale asks if there is a polynomial time algorithm (in a particular model of computation over real numbers) to place $N$ points on the sphere so that the total energy is $O(\log N)$ above the minimum energy.

Now, for specific finite values of $N$, Neil Sloane has a table of best known spherical codes with references: http://neilsloane.com/packings/

$\endgroup$
5
$\begingroup$

There is a rather comprehensive list of research articles about points on spheres and manifolds at https://my.vanderbilt.edu/edsaff/spheres-manifolds/

A nice paper is E. B. Saff, A. B. J. Kuijlaars, "Distributing Many Points on a Sphere", The Mathematical Intelligencer, Winter 1997, Volume 19, Issue 1, pp 5-11.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.