The largest polygon of diameter one

A fence of fixed length holds the most area when it is a circle, and among polygons with a fixed number of sides and fixed perimeter the regular one holds the most. Symmetry wins. Among triangles and quadrilaterals of fixed area the regular ones also have the lowest vibration frequency, and it is believed, not proved, for every number of sides. The pattern suggests a principle: when a shape is optimised, the symmetric one is optimal.

Change the constraint from perimeter to diameter — the greatest distance between any two points — and the principle half fails. Among polygons with $n$ sides and diameter one, which has the largest area? For odd $n$ the regular polygon, as Karl Reinhardt proved in 1922. For even $n$ it is never the regular polygon, from six sides on. Ron Graham found the best hexagon in 1975: lopsided, with only a mirror symmetry, and about four per cent larger than the regular one.

Why the regular hexagon wastes width #

The regular hexagon of diameter one has its three long diagonals as its diameters, all passing through the centre, and it has area $3\sqrt3/8 \approx 0.6495$. That is less than the regular pentagon’s 0.6572. Adding a side to a regular polygon of fixed diameter should help, and going from five sides to six makes things worse.

The reason is how an even regular polygon spends its diameter. Its longest distances are between opposite vertices, straight through the middle, and every other direction is shorter: across the flat sides the hexagon is only $\sqrt3/2 \approx 0.866$ wide. An odd regular polygon has no opposite vertices. Its longest distances run from each vertex to the two nearly opposite ones, and its width is nearly the same in every direction — the regular pentagon is 0.951 wide across a side, against its diameter of one. A figure of diameter one can be at most one unit wide in every direction, and the odd polygons come much closer to using all of it.

Reinhardt’s proof for odd $n$ follows the star. In outline: in an extremal polygon with an odd number of vertices the diameters can be taken to form a single star-shaped cycle through every vertex, and consecutive diameters of the star meet at angles that must add up to a fixed total, half a turn. The polygon’s area can then be written as a sum of terms each proportional to the sine of one of those angles, and the sine bends downward, so — by the same inequality that compares the curve of an average with the average of the curve — a sum of sines with a fixed total of angles is largest when all the angles are equal. Equal angles make the regular polygon. With an even number of vertices the star cannot pass through every vertex, the decomposition breaks, and the argument has nothing to say.

Graham’s hexagon recovers what the regular hexagon wastes. Its five upper vertices form a slightly flattened pentagon whose diameters close into a five-pointed star, and the sixth vertex sits below, one unit from the top vertex — six diameters in all, and a width much more evenly spread.

Finding the best polygon by climbing #

The best hexagon, octagon, decagon and dodecagon are not known in closed form in any useful sense; Graham’s hexagon has an area that is a root of a polynomial of degree ten. They are found by optimisation, and the method can be repeated.

The first stage maximises the area divided by the square of the diameter, a ratio that does not care about the polygon’s size. The diameter, a maximum of distances, has corners where two distances tie, so it is replaced by a smooth stand-in — the $p$-th root of the sum of the $p$-th powers of all distances, which approaches the maximum as $p$ grows — and $p$ is raised in stages to 640 while a gradient method climbs the ratio from a perturbed regular polygon. The second stage takes the pairs that end up within a hair of the diameter, declares them to be exactly one unit apart, and climbs the area along the surface of polygons that keep those distances exact: at each step the gradient of the area is projected onto that surface, and Newton steps pull the distances back to exactly one. The climb stops at a point where the area cannot increase without stretching some diameter — a constrained optimum, to the last digit.

The results match the published optima: 0.674981 for the hexagon, 0.726868 for the octagon — found by Charles Audet, Pierre Hansen, Frédéric Messine and Junjie Xiong in 2002, who proved it optimal with a global branch-and-bound search — 0.749137 for the decagon and 0.760730 for the dodecagon, from Didier Henrion and Messine in 2013. For pentagons and heptagons the same climb ends on the regular polygon, as Reinhardt’s theorem says it must. The figure’s zig-zag is the regular polygons’ alternation between wasting width (even $n$) and not (odd $n$), and the best even polygons sit above their regular versions, between the odd neighbours on either side.

Counting freedoms shows why the second stage is needed and why it works. A polygon with $n$ vertices has $2n$ coordinates, three of which only move it rigidly, so it has $2n - 3$ genuine degrees of freedom: nine for a hexagon. Graham’s hexagon has six pairs at distance one, which leaves three directions of motion that keep every diameter exactly one — and along those three the area is at a maximum, its gradient balanced exactly by the six taut distances. The first stage cannot see that balance, because its smoothed diameter is never exactly the true one; the second stage works on precisely the surface where the six distances are held, and there the balance is a condition that can be met to the last digit.

Random starts matter. From a single start the climb can stall at a polygon whose set of diameters is wrong — too few pairs at distance one to pin the shape — and the second stage then has nothing to hold it and wanders. Starting from several perturbed regular polygons and keeping the best result is enough, here, to reach the published value every time.

Four sides: infinitely many winners #

The quadrilateral is the case where symmetry neither wins nor loses: it ties.

A quadrilateral’s area is half the product of its diagonals times the sine of the angle between them. With diameter one, each diagonal is at most one, so the area is at most $\tfrac12$, reached exactly when both diagonals have length one and cross at a right angle — and there are infinitely many such quadrilaterals, not all symmetric. The square is a winner, but so is any kite or irregular quadrilateral built on two perpendicular unit diagonals, provided its sides stay short enough. The answer is unique only up to a whole family, and the symmetric member is not distinguished.

That tie already says that symmetry is not what decides these problems. For perimeter, convexity and a simple argument force symmetry; for diameter, the constraints are pairwise distances, and pairwise constraints can be satisfied in many asymmetric ways.

The diameters of the extreme polygons #

The pairs of vertices at distance exactly one — the diameters — are the skeleton of each extreme polygon, and drawing them shows the structure the optimisation finds.

In the regular pentagon every vertex has two diameters and they close into a single cycle through all five vertices, the five-pointed star; Reinhardt’s proof turns on that cycle. In the best hexagon the diameters form a cycle of five, also a star, with the sixth vertex attached by one more diameter; in the best octagon, a cycle of seven with the eighth attached the same way. Graham conjectured that this is the shape for every even number of sides — an odd cycle of diameters through all but one vertex, plus one pendant diameter — and Michael Foster and Tibor Szabó proved in 2007 that it is.

The pattern is a statement about parity. An odd cycle of diameters is what makes a polygon nearly as wide in every direction as it is long; a polygon with an odd number of vertices can put all its vertices on such a cycle, and the regular one does. With an even number of vertices one is left over, and the best that can be done is to hang it from the cycle. The regular even polygon does something else entirely — its diameters form a perfect matching through the centre — and loses.

How far each polygon falls short of the disc #

Every figure of diameter one has area at most $\pi/4$, the area of the disc of diameter one. That is the isodiametric inequality, proved by Ludwig Bieberbach in 1915, and the polygons approach it from below.

The odd regular polygons approach the disc like $1/n^2$, the rate at which a polygon inscribed in a circle approaches it. The regular even ones fall short by much more at every $n$, and the best even polygons close most of that gap, landing between their odd neighbours. The shortfalls also show how little the even-sided optimisation gains in absolute terms at large $n$: by twelve sides the regular dodecagon and the best one differ by about one hundredth, and the problem becomes a question about the third decimal place.

Bieberbach’s proof uses Steiner’s symmetrisation, sliding every chord to the middle of a line: symmetrising a figure keeps its area and does not increase its diameter, and repeated symmetrisation in many directions turns any figure into a disc. For the disc, symmetry wins outright. It is only among polygons with a fixed number of vertices that symmetrisation is not available — a symmetrised hexagon is generally not a hexagon — and the even cases are free to be lopsided.

Diameter one, any shape #

Among all figures of diameter one, polygons compete with curved shapes, and the curved ones do surprisingly well.

The Reuleaux triangle, the curved triangle made of three circular arcs centred at the corners of an equilateral triangle, has constant width one and hence diameter one, and area $(\pi - \sqrt3)/2 \approx 0.7048$. It beats every polygon with six sides or fewer, including Graham’s hexagon, and loses only from the heptagon on. That is the more striking because the Reuleaux triangle is the figure of constant width with the least area — the worst of the shapes that are one unit wide in every direction — and it is still better than any hexagon at filling a diameter of one. Corners cost a great deal; curvature recovers it.

When symmetry wins elsewhere #

The split verdict is not peculiar to diameter. Where charges settle on a sphere, four, six and twelve repelling charges sit at the corners of regular solids, but eight do not sit at the corners of a cube — they twist into a square antiprism — and five choose a bipyramid over anything more regular. In the cheapest walls for equal rooms, the symmetric honeycomb wins outright, in the plane, and the proof took until 1999. In each case symmetry is the natural first guess, and whether it is right depends on a detail of the constraint that has nothing visibly to do with symmetry: here, whether the number of vertices can all sit on one odd cycle of diameters.

What these problems share is that the constraints are many small conditions — pairwise distances, pairwise repulsions, shared walls — rather than one global quantity like perimeter. A global constraint can usually be improved by symmetrising, because symmetrising averages; a family of pairwise constraints can be satisfied in asymmetric ways that no averaging argument reaches, and then the optimum may be lopsided.

The isodiametric inequality also has the stability property that a nearly optimal figure is nearly round: a figure of diameter one whose area is close to $\pi/4$ must be close to a disc. The best polygons are the extreme examples of that: as their number of sides grows, their area approaches the disc’s, and their shapes, lopsided or not, are squeezed towards the circle.

The same question in space #

In three dimensions the isodiametric inequality still holds — the ball of diameter one has the most volume of any solid of diameter one — and the polyhedral question has hardly been touched. Which polyhedron with a given number of vertices and diameter one has the largest volume is known only for very few vertices, and the regular solids are no guide: the regular octahedron and icosahedron have their diameters through the centre, like even regular polygons, and so waste width. Constant width in space is itself subtle — the obvious analogue of the Reuleaux triangle, the intersection of four balls at a tetrahedron’s corners, is not of constant width at all — and the polyhedral diameter problem inherits that subtlety with nothing like Reinhardt’s theorem to start from.

What the optimisation cannot show #

Every optimum on this page is a computed number, and computation finds good polygons without proving them best. The climb from random starts reaches a constrained local optimum; that it is the global one for six sides is Graham’s theorem, for eight sides Audet, Hansen, Messine and Xiong’s, and for ten and twelve rests on Henrion and Messine’s global computations — each a method that exhausts the possibilities rather than climbing. The figures show that the climb agrees with those proofs. They would not have discovered a better polygon if one existed, and they cannot rule one out for larger $n$.

The figures also take on trust that the right set of diameters has been found. The active-set stage fixes the pairs that the first stage left close to one; if it fixes too few, the result is not a polygon of diameter one, and such results are discarded rather than corrected. A different set of diameters would give a different candidate, and the method tests only the sets the first stage happens to approach.

Still open: the optimum for many sides #

What is the largest area of an $n$-gon of diameter one for even $n$ beyond twelve? The shape of its diameters is known — Foster and Szabó’s theorem fixes it as an odd cycle through all but one vertex plus a pendant diameter — but within that shape the optimum is still a finite-dimensional problem with many local optima, and the certified answers stop at twelve sides. Numerical optima for larger even $n$ can be found by climbing, as here, without a certificate that they are best. What is wanted is a description of the optimal polygons for every even $n$, or at least of how their area approaches $\pi/4$, and neither is known.

A related question asks for the largest perimeter rather than area. There the answer is known whenever $n$ has an odd factor — the best polygons have all their sides equal, though they need not be regular — and for powers of two it is known only in the first few cases. The two questions differ in which constraint binds, and they are an instance of the general lesson of these problems: whether the symmetric shape is optimal depends on the constraint far more than on the shape.

Symmetry wins by parity #

Among $n$-gons of diameter one, the regular polygon has the most area exactly when $n$ is odd. With an odd number of vertices the diameters can close into a single odd cycle, as in the regular pentagon’s star, and the polygon is nearly as wide in every direction as it is long; with an even number one vertex is left over, the regular polygon spends its diameter through the centre, and a lopsided shape — Graham’s hexagon at 0.674981, the octagon at 0.726868 — does better. Four sides tie in a whole family at area ½, the disc beats everything at π/4, and the Reuleaux triangle beats every hexagon.