To find the Largest Regular n-gon contained in a given convex region

1. Given a general convex region C, to find the largest regular polygon that is contained in it (shared boundaries allowed). Basically, one needs to find that particular value of n for which a regular n-gon contained in C has the largest area.

Example: If C is an isosceles right triangle of area 1 unit, the largest square (n=4) contained in it has area 1/2 unit and this appears more than the area of the largest equilateral triangle (n=3) or largest circle (n -> infinity) that is contained in C.

1. A related question: Given a value of n, can one find some triangle such that the largest regular polygon inscribed in the triangle has exactly n sides? One guess is that n cannot be arbitrarily large if C is restricted to be some triangle - iow, that for any triangle, the largest contained regular n-gon cannot be the incircle.

2. Another related question: Given a convex region C and a positive integer n>=3. Let A(n) be the area of the largest n-gon that can be drawn inside C. What could one say in general about the behavior of A(n) as n increases? For example, does A(n) have exactly one local maximum (which is also the global max) for any C?

Further remark: We can think of a classification of all convex regions (including non-polygonal ones) into a countable number of categories based on which regular n-gon, when inscribed in the convex region, gives max area.

Regarding question 2, above, here is a guess: (Qn: Given a value of n, can one find some triangle such that the largest regular polygon inscribed in the triangle has exactly n sides?) Take an isosceles obtuse triangle with largest angle = 180 - 360/n. For it, the largest inscribed regular polygon will have n sides. Eg: for any obtuse triangle with largest angle 108, the largest inscribed regular n-gon is the regular pentagon.

Note: This guess looks likelier to be valid for odd n. But it does not seem useful for large n. Indeed, if we plug in a large value of n into 180 - 360/n, ie. considering isosceles triangles with large obtuse angle, the square (n=4) would be a larger inscribed regular polygon than a regular n-gon.

1 Answer

Not a full answer, just two remarks.

(1) Literature. There is an old paper that finds a largest inscribed equilateral triangle, and a largest inscribed square, but these results do not straightforwardly generalize:

DePano, A., Yan Ke, and J. O’Rourke. "Finding largest inscribed equilateral triangles and squares." In Proc. 25th Allerton Conf. Commun. Control Comput, pp. 869-878. 1987.

Unfortunately, I no longer have access to my own article. :-/ My recollection is that we achieved $$O(n^3)$$ time for equilateral triangles and $$O(n^2)$$ time for squares, for a convex polygon of $$n$$ vertices.

See Mathworld: In unit square, side $$s=\sec(15^\circ)$$ and area $$A=2\sqrt{3}-3$$.

Another relevant paper from the same period:

Fekete, Sandor P. "Finding all anchored squares in a convex polygon in subquadratic time." (1992). Download author's PDF.

(2) Question 3: "does $$A(n)$$ have exactly one local maximum (which is also the global max) for any $$C$$?"

No, not always. Let $$C$$ be an equilateral triangle. Then the global max is $$A(3)$$, but $$A(6)$$ is a local max:

$$A(3) > A(4) < A(6) > A(12)$$.
So perhaps you should exclude $$C$$ being a regular polygon itself.

• A nice and simple example. This indicates A(n) could in general (for a general C) can have many ups and downs as n goes from 3 to infinity - although an explicit example would be nice. And just leaving out the case of C being a regular polygon might not help much. For example, C can be a trapezium formed by chopping off just a vertex and a tiny bit from an equilateral triangle. n=3 will still be the global maximum for A(n) and for other values of n, all regular polygons in above picture would go through fine. – Nandakumar R Sep 20 '19 at 18:51
• @NandakumarR: Good point re trapezium. – Joseph O'Rourke Sep 20 '19 at 19:52