41
$\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.

Improve this question
$\endgroup$
3
  • 17
    $\begingroup$ This problem is unsolved for large number of points. $\endgroup$
    – Alexandre Eremenko
    Commented Jul 29, 2015 at 11:26
  • 10
    $\begingroup$ For a couple of related papers, see arXiv:math.MG/0611451 and arXiv:math/0607446. $\endgroup$
    – Richard Stanley
    Commented Jul 29, 2015 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
    Commented Jul 30, 2015 at 11:30

3 Answers 3

Reset to default
42
$\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).

Improve this answer
$\endgroup$
5
  • 8
    $\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$
    – user21349
    Commented Jul 29, 2015 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
    Commented Jul 29, 2015 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$
    – user21349
    Commented Jul 29, 2015 at 23:11
  • 3
    $\begingroup$ $n=20$ is not a dodecahedron, why not and who solved that? $\endgroup$
    – Raphael J.F. Berger
    Commented Dec 31, 2017 at 9:29
  • 1
    $\begingroup$ @Rudi_Birnbaum It suffices to check that two closest vertices in a dodecahedron (inscribed in the sphere) are at a distance closer than $0.647046$, since one can give a spherical code with separation larger than this (see neilsloane.com/packings). $\endgroup$
    – Josiah Park
    Commented Nov 26, 2019 at 22:24
15
$\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/

Improve this answer
$\endgroup$
8
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .