Wolfram Blog
Ed Pegg Jr

Biggest Little Polyhedron—New Solutions in Combinatorial Geometry

May 20, 2015 — Ed Pegg Jr, Editor, Wolfram Demonstrations Project

In many areas of mathematics, 1 is the answer. Squaring a number above or below 1 results in a new number that is larger or smaller. Sometimes, determining whether something is “big” is based on whether a largest dimension is greater than 1. For instance, with sides of length 13,800 km, Saturn’s hexagon would be considered big. A “little polygon” is defined as a polygon where 1 is the maximum distance between vertices. In 1975, Ron Graham found the biggest little hexagon, which has more area than the regular hexagon, as shown below. The red diagonals have length 1. All other diagonals (not drawn) are smaller than 1.

Regular hexagon, biggest little hexagon, biggest little octagon showing lengths of 1

I’ve often wondered what the biggest little polyhedra would look like. Mathematica 10 introduced Volume[ConvexHullMesh[points]], so I thought I could solve the problem by picking points at random. Below is some code for picking, calculating, and showing a random little polyhedron. If the code is run a thousand times, one of the solutions will be better than the others. Here, I ran it three times. One of these three solutions is (probably) better than the other two.

Random solutions for picking points on a polyhedron

With randomly selected points, images like the following emerge from the better solutions. I posted these on Wolfram Community under the discussion Biggest Little Polyhedra, and got some useful comments from Robin Houston and Todd Rowland. I thought of using results from “Visualizing the Thomson Problem” for solutions. In the Thomson problem, electrons repel each other on a sphere. Twelve repelling points move to the vertices of an icosahedron, which is inefficient for BLP, since all the longest distances pass through the center of the bounding sphere, just like the regular hexagon in the polygon case. I modified the Thomson code so that points repelled each other and all polar opposites, and that gave good starting values.

Starting values using modified Thomson code

Four points need a regular tetrahedron, with volume Square root of 2/12= 0.117851.
Five points need a unit equilateral triangle with a perpendicular unit line, with volume Square root of 3/12 = 0.1443375; solved in 1976 [1].

Regular tetrahedron and equilateral triangle points

I’ll use the name 6-BLP for the biggest little polyhedron on 6 points. In 2003, the volume for 6-BLP was solved to four decimals of accuracy [2, 3]. Graphics for 6-BLP and 7-BLP are below, with red lines for the unit diagonals.

6-BLP and 7-BLP

To find these on my own, I first picked the best solutions out of a thousand tries, then used simulated annealing to improve the solutions. For each of the points in the good solution, I introduced a tiny bit of randomness to try to find a better solution, thousands of times. Then I introduced a tinier bit of randomness, over and over again. Some of these solutions seemed to go to a symmetrical solution. For example, with seven points, the best solution seemed to be gradually drifting toward this polyhedron, with a value of r of about a half, which represents the relative size of the upper triangle △456.

Symmetrical solution for random polyhedron with seven points

The exact volume can be determined by the tetrahedra defined by the points {{2,3,4,7}, {2,4,6,7}, {5,4,7,6}}, with the volumes of the first two being tripled for symmetry. Look at the volumes of the tetrahedra, and switch any two numbers in a tetrahedron with negative volume.

Determining the exact volume of the tetrahedra by defined points

After changing the parity of the last tetrahedron, we can calculate the exact r that gives the exact optimal volume. In the same way, we’ll also solve a few others.

Calculating r for solution6, solution7, solution8, solution9

The solution for 16-BLP takes more than a minute, so I’ve separated it out.

Solution for 16-BLP

The first value in the solutions is the optimal volume as a Root object, and the second is the optimal value of r. Here’s a cleaner table of values.

Table of values for optimal value of r

That is far beyond anything I could have solved by hand. With random selection, annealing, symmetry spotting, Solve[], and Maximize[], I was also able to find the exact n-BLP (biggest little polygon) for n = 6, 7, 8, 9, and 16.

Here are a few views of the 8-BLP, with the red tubes showing unit-length diagonals.

Views of the 8-BLP with the red tubes showing unit-length diagonals

Some views of 9-BLP:

Views of 9-BLP with the red tubes showing unit-length diagonals

Some views of 16-BLP:

Views of 16-BLP with the red tubes showing unit-length diagonals

The labeled 8-BLP below features perpendicular unit lines 1-2 and 3-4 above and below the origin. The labeled 9-BLP below features stacked triangles △123, △456, and △789.

8-BLP featuring perpendicular line units and 9-BLP featuring stacked triangles

The labeled 16-BLP below features a truncated tetrahedron on points 1-12 and added points 13-16.

16-BLP featuring a truncated tetrahedron

Fairly complicated, right? With sphere point picking, random numbers –Pi to Pi and –1 to 1 can produce randomly distributed points on a unit sphere. Points on a unit sphere can be mapped back to points in the (–Pi to Pi, –1 to 1) rectangle. With the solutions for 8, 9, and 16, here’s what happens.

Sphere point picking for solutions with 8, 9, and 16 points

For 10-BLP, I haven’t been able to find an exact solution, but I did find a numerical solution to any desired level of accuracy. If anyone can find a root object for this, let me know. Open up the notebook version to see a rather difficult equation in the Initialization section.

10-BLP equation

Here’s a labeled view of 10-BLP from two different perspectives.

Two different perspectives of the labeled view of 10-BLP

In a similar fashion, a numerical solution for 11-BLP can be found.

11-BLP equation

Here are two views of 11-BLP.

Two views of 11-BLP

Have I really solved these? Maybe not. For these particular symmetries, I’m sure I’ve found the local maximum. For example, here’s a function with a local maximum of 5 at the value 1.

Plot showing found local maximum of 5

Plot a bit more, and the global maximum of 32 can be found at value -2.

Plot showing found global maximum of 32

In the related Thomson problem, there’s a proof that the 12 vertices of an icosahedron give a minimum energy configuration for 12 electrons. But 7, 8, 9, 10, 11, and 13+ electrons are all considered unsolved. The Kepler conjecture suggested that hexagonal close packing was the densest arrangement of spheres, but a complete formal proof by Thomas Hales wasn’t completed until August 10, 2014. The densest packing of regular tetrahedra, the fraction 4000/4671 = .856347…, wasn’t found until July 27, 2010, and still isn’t proven maximal. Take any solution claims with a grain of salt; geometric maximization problems are notoriously tricky.

For months, my best solution for 11 points was in an asymmetric local maximum. Some (or most) of the following solutions are likely local instead of global, but which ones? With that caveat, we can look at best known solutions for 12 points and above.

12-BLP seems to be the point 12, the slightly messy heptagon 11-6-7-10-8-5-9, and the quadrilateral 1-4-3-2.

13-BLP seems to be the point 13, the slightly messy heptagon 12-8-10-6-7-9-11, and the messy pentagon 1-2-3-4-5.

My attempts to add symmetry have resulted in figures with a lower volume.

12-BLP and 13-BLP

So far, my best solutions for a 14-BLP seems to have a lot of symmetry, but I haven’t solved it. I spent some time optimizing a point-heptagon-heptagon solution for a 15-BLP, only to watch my randomizer “improve” it relentlessly by increasing volume while sacrificing symmetry.

14-BLP and 15-BLP

17-BLP, 18-BLP—I believe 17-BLP has nice symmetry.

19-BLP, 20-BLP—20 is not the dodecahedron, due to inefficient unit lines through the center.

Symmetry for 17-BLP, 18-BLP, 19-BLP, and 20-BLP

The snub cube and half the vertices of the great rhombicuboctahedron both have lower volume than 24-BLP.

Snub cube and half the vertices of the great rhombicuboctahedron have lower volume than 24-BLP

21-BLP, 22-BLP—Lots of 7- and 9-pointed stars.

23-BLP, 24-BLP—My best 24-BLP has tetrahedral symmetry.

21-BLP, 22-BLP, 23-BLP, 24-BLP symmetry

Here’s some of the symmetry in the current best 24-BLP. Points 1-12 and 13-24 have respective norms of 0.512593 and 0.515168.

Symmetry in the current best 24-BLP

16-BLP, 17-BLP—Letting the unit lines define polygons. 16-BLP contains many 7-pointed stars.

16-BLP contains 7-pointed stars

The same polyhedra shown as solid objects, using ConvexHullMesh[]. That’s BLP 9-10-11-12, 13-14-15-16, 17-18-19-20, 21-22-23-24.

Polyhedra shown as solid objects using ConvexHullMesh

Here’s the current table of the best known values.

Current table of best known values

Here are the best solutions I’ve found so far for 4 to 24 points.

Best solutions for 4 to 24 points

Let the points be centered so that the maximal distance from the origin is as small as possible. The below scatterplot shows the distance from the origin for vertices of each polyhedron, from 8 to 24 vertices.

Distance from origin for vertices scatterplot

Mathematica 10.1 managed to exactly solve 6-BLP, 7-BLP, 8-BLP, 9-BLP, and 16-BLP. It found numerically exact solutions for 10-BLP and 11-BLP, and made good progress for up to 24 points. That gives solutions for seven previously unsolved problems in combinatorial geometry, all by repeating Volume[ConvexHullMesh[points]]. What new features have you had success with?

References

[1] B. Kind and P. Kleinschmidt, “On the Maximal Volume of Convex Bodies with Few Vertices,” Journal of Combinatorial Theory, Series A, 21(1) 1976 pp. 124-128.
doi:10.1016/0097-3165(76)90056-X

[2] A. Klein and M. Wessler, “The Largest Small n-dimensional Polytope with n+3 Vertices,” Journal of Combinatorial Theory, Series A, 102(2), 2003 pp. 401-409.
doi:10.1016/S0097-3165(03)00054-2

[3] A. Klein and M. Wessler, “A Correction to ‘The Largest Small n-dimensional Polytope with n+3 Vertices,’” Journal of Combinatorial Theory, Series A, 112(1), 2005 pp. 173-174.
doi:10.1016/j.jcta.2005.06.001

Download this post as a Computable Document Format (CDF) file.

Posted in: Mathematics
Leave a Comment

One Comment




Leave a comment

Loading...

Or continue as a guest (your comment will be held for moderation):