How can one generate a distribution of N points over the surface of a sphere so that the all N voronoi cells have the same area? Which is the best algorithm for this?
Optimal distribution of points over the surface of a sphere
-
1You need to describe this rather more precisely. Do you want the points randomly distributed or as far apart as possible? For example, if you had two points you might want the second to be exactly opposite the first, with no randomness in that relationship. And what do you mean by distance between each pair of points to be as long as possible? For example the shortest distance between any two points, or the total sum of the squares of the distances between all pairs of points? – 2011-09-21
-
0thanks, now I guess it is more clear – 2011-09-21
-
0I doubt that this measures what you want it to measure. For instance, if you have three points, the maximal sum of squared distances is achieved if two points are the same and the third is opposite to them (for a sum of $2(\pi r)^2$), whereas what I suspect you'd want is for the three points to form an equilateral triangle on a great circle (for a sum of $(4/3)(\pi r)^2$). – 2011-09-21
-
1Related to http://math.stackexchange.com/questions/31619/well-separated-points-on-sphere – 2011-09-21
-
0ok, I reedited it again – 2011-09-21
2 Answers
The following is a classical paper on distributing points on a sphere:
Edward Saff, Arno Kuijlaars, Distributing Many Points on a Sphere, The Mathematical Intelligencer, Volume 19, Number 1, 1997, pages 5-11.
-
0is it there any software implementation for this? – 2011-09-22
-
0Yes, if you search on the names of the authors and the title of the paper I gave, you'll find some implementations. – 2011-09-22
-
0The link is dead – 2018-04-22
-
0@ athos : not anymore. – 2018-04-22
This is a classical problem, and let me just explain what is and isn't possible.
Think of the five platonic solids. Tetrahedron, cube, octahedron, dodecahedron, and the icosahedrone. They have respectively: 4, 6, 8, 12 and 20 vertices. If you were to find a way of getting say, 7 points perfectly distributed on a sphere, guess what? You would have discovered a new platonic solid!
All you would have to do is just connect all the vertices with edges, and voilà, you would have found a sixth platonic solid. It's already been proven that this impossible, so..
You are going to have to come to grips with the sad reality that you won't find a way of getting an arbitrary number of points evenly distributed on a sphere, other than those mentioned. There are some pretty good estimates of even distributions, but other than the cases already mentioned it is not possible.