Optimal Point Placement Problems

Roundest Polyhedra

The Isoperimetric Problem for Polyhedra, first proposed in the 18th century by Simon Antoine Jean L'Huilier, is the problem of finding the convex polyhedron with a given number of faces that has the smallest surface area to volume ratio: A3/V2. In the 19th century Lorenz Lindelöf proved that such polyhedra must have all their faces tangent to a sphere at the face centroids. Hermann Minkowski proved that such solutions do indeed exist.

In his 1935 paper Michael Goldberg conjectured that for all n except n=11 and 13 the solutions are medial polyhedra: simple polyhedra (three faces around each vertex), with faces being either b-gons or (b+1)-gons. (There are no medial polyhedra with 11 or 13 faces.) Prior to his paper solutions had been proven only for n=4 (regular tetrahedron), 5 (triangular prism) and 6 (cube), and a partial proof had been made for 7 (pentagonal prism). Goldberg provided a proof for 12 (regular dodecahedron). He also provided putative solutions for n up to 16, and for 20, 32 and 42.

In his 1986 paper and supplement Alan Schoen reported on his search for putative solutions using a Monte Carlo method. The first case of note is for n=25 which has C1 (that is no) symmetry. (Goldberg speculated on this possibility in his paper on the Isoperimetric Problem.) For n=32 and 42 Goldberg had proposed polyhedra having icosohedral symmetry: members of what are now known as Goldberg polyhedra. Schoen's search results supported Goldberg's Ih solution for 32 but came up with a better, D5h solution for 42.

I recreated Alan's Monte Carlo program in 2015. The increase in computing speeds in the intervening three decades allowed for useful runs up to n=200: Table 1-1: Summary of Monte Carlo runs for n=4 to 200. This method works for such large n apparently due to several factors: the number of polyhedra meeting the Lindelöf conditions grows much more slowly with increasing n than does the number of distinct simple polyhedra, and the routine tends to exclude polyhedra whose tangent points are not fairly uniformly distributed on the surface of a sphere.

While Goldberg's conjecture regarding solutions being medial polyhedra appears to be incorrect it may still be a useful approximation. To limit the number of cases needing to be checked, only medial polyhedra having their 12 pentagons near the vertices of the regular icosahedron were considered. These were then run (for n=186 to 504) through Schoen's roll-toward centroid routine to attempt to "stabilize" them. Polyhedra which did not converge were discarded.

In order to extend the search for cases having heptagonal faces, it is noted that a patch of two pentagonal faces and a heptagonal face on an n faces polyhedron may be substituted for a patch consisting of one pentagonal and three hexagonal faces to obtain an n-1 polyhedron. This procedure was performed on the 100 best results of the previous stage until 12 heptagons had been added: Table 1-2: Summary of constratined search runs.

Collection of best known roundest polyhedra.

While medial polyhedra having icosahedral symmetry, the Goldberg polyhedra, are not neccessarily the best, they may still offer clues as to what makes a polyhedron good: Table 1-3: Goldberg Polyhedra. It is well known that there exist many Goldberg pairs. As G(a,b) and G(b,a) are chiral forms of the same polyhedron when a≠b and neither are zero we may consider only a≠0, b≥0, a≥b. Note that the member of each pair which has a greater b/a also has a greater IQ.

By making use of rotational icosahedral symmetry computation of the Goldberg polyhedra was reduced by a factor of 60 to produce: Table 1-4: Goldberg Pairs. This was to look for a possible ideal b/a less than one. In all cases a=b is still best. Several statistics were gathered by this program. The relative size of the 12 pentagons decreases with increasing n. There is more variability in hexagon sizes for smaller values of b/a.

The Goldberg polyhedra may be viewed as a mapping of a hexagonal lattice onto a sphere. They have three zones. The first consists of the twelve pentagons corresponding to the vertices of the master icosahedron, the defects neccessary for the spherical shape. The next are 30 parallelograms corresponding to the edges of the master polyhedron. For G(a,b), the a and b define the lengths of the parallelogram edges. The last are 20 triangles for the 20 icosahedron faces.

There are two "degenerate" cases, both having Ih symmetry. When b=0 there are effectively no parallelogram zones. These seem to be the worst cases, possibly due to mapping distortion over the relatively large triangles. Where a=b the parallelogram zones squeeze out the triangular zones, and these seem to be the best cases.

The addition of heptagon-pentagon pairs for polyhedra having more than 200 faces often results in higher IQ. This has been noted for the minimum energy point placement problems. For example, see Hardin & Saff.

Lengyel, Gáspár & Tarnai have looked at the roundeds polyhedra constrained to having the higher order symmetries: tetrahedral, octahedral, and icosahedral. This page updates their list.

Maximal Volume Polyhedra

The problem of finding the minimum volume polyhedra tangent to a sphere is equivalent to the Isoperimetric Problem for Polyhedra. The dual of this problem is finding the maximum volume polyhedra having all their vertices on the surface of a sphere. In 1963 Grace used a computer search to find a solution for n=8. In 1970 Berman and Hanes proved solutions for n=4 through 8. In 1994 Hardin, Sloane and Smith searched for putative solutions for n≤130.

My approach is based on the assumption that as both problems are "optimal point placement" problems, what is a good case for one would likely be good for the other. I therfore took the duals of the 100 best roundest polyhedra and optimized them for volume: Table 2-1: Summary of maximal volume polyhedra.

Collection of best known maximal volume polyhedra.


  1. D. M. Aubertin, Optimization of Four-Dimensional Polytopes, Masters thesis, Southern Illinois University, Carbondale, Illinois, (1989).
  2. J. D. Berman & K. Hanes, Volumes of polyhedra inscribed in the unit sphere in E3, Mathematische Annalen vol. 188 (1970), pp. 78-84.
  3. P. W. Fowler, J. E. Cremona & J. I. Steer, Systematics of bonding in non-icosahedral carbon clusters, Theor Chim Acta, vol 73 1–26 (1988).
  4. M. Goldberg, The Isoperimetric Problem for Polyhedra, Tohoku Mathematics Journal vol. 40 (1935), pp. 226-236.
  5. M. Goldberg, A Class of Multi-Symmetric Polyhedra, Tohoku Mathematics Journal vol. 43 (1937), pp. 104-108.
  6. D. W. Grace, Search for largest polyhedra, Math. Comp, 17, 197–199 (1963).
  7. D. P. Hardin & E. B. Saff, Discretizing Manifolds via Minimum Energy Points, Notices Amer. Math. Soc., vol 51 1186–1194 (2004).
  8. D. P. Hardin, T. Michaels & E.B. Saff, A Comparison of Popular Point Configurations on S2, Dolomites Research Notes on Approximation, vol 9 16–49 (2016).
  9. R. H. Hardin, N. J. A. Sloane & W. D. Smith, Spherical Codes, book in preparation. neilsloane.com/maxvolumes/index.html
  10. V. Klee, Viewer's Manual to accompany the film Shapes of the Future - Some Unsolved Problems in Geometry, Part II: Three Dimensions, distributed by Modern Learning Aids (1972).
  11. D. Knuth, ran_array, lagged Fibonacci sequence rng, www-cs-faculty.stanford.edu/~knuth/programs.html#rng (2012).
  12. A. Lengyel, Z. Gáspár & T. Tarnai, The Roundest Polyhedra with Symmetry Constraints, Symmetry 2017, 9(3), 41; doi:10.3390/sym9030041
  13. S. Lhuilier, De relatione mutua capacitatis et terminorum figurarum etc., Varsaviae (1782).
  14. L. Lindelöf, Propriétés générales des polyhèdres etc., Bull. Acad. Sci. St. Pétersbourg 14 (1869) p.257.
  15. L. Lindelöf, Recherches sur les polyèdres maxima, Series: Acta Soc. Sci. Fenn. vol 24, Officina Typographica Societatis Litterariae Fennicae, Helsingfors, 1899.
  16. H. Minkowski, Allgemeine Lehrsätze über die convexen Polyheder, Göttingen, Nach. Ges. Wiss. Math. phys. (1897), pp. 198-219.
  17. A. Schoen, A defect-correction algorithm for minimizing the volume of a simple polyhedron which circumscribes a sphere, in Proc. of 2nd Annual ACM Symposium on Computational Geometry, Yorktown Heights, N.Y., 2–4 June 1986, ACM Press, 1986, p.159.
  18. A. Schoen, Supplement to a ‘defect-correction algorithm for minimizing the volume of a simple polyhedron which circumscribes a sphere’, Technical report No 86-01*, Department of Computer Science, Southern Illinois University, Carbondale, Illinois, (1986), p.1.
  19. S. Vigna, An Experimental Exploration of Marsaglia's xorshift Generators, Scrambled, ACM Transactions on Mathematical Software, (2014) 42. 10.1145/2845077.
  20. T. Tarnai, Z. Gáspár & A. Lengyel (2013) From spherical circle coverings to the roundest polyhedra, Philosophical Magazine, 93:31-33, 3970-3982, DOI: 10.1080/14786435.2013.800652

Wayne Deeter - wrd@deetour.net

Last modified: June 10, 2018