# Minmax problem for polygons

Let $\text{Pol}_n$ be the set of all convex polygons on a plane with $n$ sides. For $P\in \text{Pol}_n$ denote by $\text{Tr}(P)$ the set of all triangles whose vertices are some vertices of $P$. I want to find an explicit formula for the function $$\Phi(n)=\inf\limits_{P\in \text{Pol}_n}\max\limits_{T\in \text{Tr}(P)}\frac{\text{area}(T)}{\text{area}(P)}$$ It is not hard to prove that $\Phi(3)=1$, $\Phi(4)=1/2$. For $n\geq 5$ we have an estimation $\Phi(n)\geq 1/(n-2)$.

-
Suppose $\triangle ABC$ has maximal area among sub-triangles of $P$. Among vertices of $P$, $A$ is at maximal distance from line $BC$: that is, $P$ lies between the line through $A$ parallel to $BC$ and the reflection of that line in $BC$. Likewise, $B$ (resp $C$) is at maximal distance from line $CA$ (resp $AB$). The parallel-line boundaries determine $\triangle A'B'C'$ for which $\triangle ABC$ is the (similar) midpoint triangle. Thus, $|P| \le |\triangle A'B'C'| = 4 \; |\triangle ABC|$, so that $\frac{1}{4} \le \; \frac{|\triangle ABC|}{|P|} = \max_T \frac{|T|}{|P|}$, regardless of $n$. –  Blue Dec 12 '11 at 9:07
By the way: For $\frac{|\triangle ABC|}{|P|}$ to attain the minimum $\frac{1}{4}$, we'd need that $P$ covers the entirety of $\triangle A'B'C'$. This would require each of $A'$, $B'$, and $C'$ to be vertices of $P$; but then $\triangle A'B'C'$ is itself a sub-triangle of $P$, contradicting $\triangle ABC$'s maximality. Thus, the maximal ratio of areas is strictly greater than $\frac{1}{4}$. Further, it seems the infemum is also strictly greater than $\frac{1}{4}$, since $P$ can't even have three vertices "close" to $A'$, $B'$, and $C'$ (or even just two vertices close to two of them). –  Blue Dec 12 '11 at 15:35
On the other hand, for a regular $n$-gon with $n$ large the maximal triangle has area approximately $3 \sqrt{3}/(4 \pi)$ times the area of the $n$-gon. So $\limsup_{n \to \infty} \Phi(n) \le \frac{3 \sqrt{3}}{4 \pi}$. –  Robert Israel Dec 19 '11 at 21:03
Just to acknowledge the cases explicitly: Clearly, if $\Phi(3)=1$. If $n=4$, we minimize the ratio by taking the fourth vertex to be one of $A'$, $B'$, or $C'$, so that $\Phi(4) = 1/2$. Indeed, if, for any $n$, $P$ contains any one of those vertices, say $A'$, then its boundary must exactly match that of parallelogram $A'BAC$ (with sub-divided edges), giving ratio $1/2$. Thus, we can concentrate on situations where $P$ contains none of those vertices; and where $P$ has vertices in at least two of $\triangle A'BC$, $\triangle AB'C$, and $\triangle ABC'$. –  Blue Dec 20 '11 at 8:17
It seems that the formula would be the same if we take vertices of triangle from boundary of P, or points bounded by P. Would this help the computation? –  FiniteA Dec 23 '11 at 1:48

Addendum: Later in comments there was found a counterexample for the formula given below.

Here's an educated guess: For $n\gt3$.

$$\Phi(n)=\begin{cases}\phi(k,n-1)&n=3k\\\phi(k,n)&n=3k+1\\\phi(k+1,n)&n=3k+2\end{cases}\quad(k\in\mathbb N)$$

with

$$\phi(k,n)=\frac{8\sin^3(\pi k/n)\cos(\pi k/n)}{n\sin(2\pi/n)}\;.$$

I don't have a proof for this, but some numerical evidence and some plausibility arguments.

Similar polygons lead to the same ratio. Thus we can restrict the vertices to a compact subset of the plane. If we allow degenerate polygons (with coinciding vertices), it follows that the infimum is actually attained for some minimizing polygon.

In such a minimizing polygon, all vertices must be vertices of a maximal triangle, since we could freely move any vertex that isn't without increasing the maximal triangle area, and by moving it outward we could increase the area of the polygon and thus reduce the ratio.

If a vertex is part of only one maximal triangle, we can freely move it parallel to the opposite edge of that triangle without changing the altitude and thus the area of that triangle. This can't move the vertex outward, since again we could otherwise increase the area of the polygon without increasing the area of a maximal triangle. Thus the line connecting the two neighbouring vertices must be parallel to the opposite edge of the maximal triangle.

Now if a second one of the vertices of that maximal triangle is also only part of that one maximal triangle, the same arguments apply to that vertex. But since we've changed the direction of the edge opposite it (by moving the first point), that edge is now no longer parallel to the line connecting the vertices neighbouring the second point, and the second point can therefore now be moved outward parallel to the opposite edge without increasing the area of a maximal triangle. It follows that in any maximal triangle of a minimizing polygon, at most one of the vertices can be part of only that one maximal triangle.

On the other hand, if a vertex is part of two maximal triangles with opposite edges in different directions, it isn't free to move without increasing the area of at least one of the maximal triangles. Whether this would decrease the area ratio depends on the details of the opposing edges and the line connecting the neighbouring vertices.

Now consider regular $n$-gons with $n=3k+m$ vertices. For $m=1$, each vertex is part of three different maximal triangles, each with vertices $k$, $k$ and $k+1$ vertices apart. For $m=2$, each vertex is also part of three different maximal triangles, each with vertices $k$, $k+1$ and $k+1$ vertices apart. We can check for $n=4$ and $n=5$ that moving a vertex outward would increase the area ratio, and it's clear that it will then also do so for greater $n$. Thus in these cases a regular $n$-gon is a locally minimizing polygon. I can't exclude the possibility that there's a lower global minimum with less symmetry, but it seems unlikely, especially considering the many constraints just derived.

However, for $m=0$, each vertex is part of only one maximal triangle, so in this case the regular $n$-gon isn't a minimizing polygon. To guess what might instead be a minimizing $3k$-gon, let's consider the area ratios of regular $n$-gons. In terms of the function $\phi$ defined above, these are

$$\Phi_{\text{reg}}(n)=\begin{cases}\phi(k,n)&n=3k\\\phi(k,n)&n=3k+1\\\phi(k+1,n)&n=3k+2\end{cases}\quad(k\in\mathbb N)\;.$$

Plotting this sequence shows that $\Phi_{\text{reg}}(3k-1)\lt\Phi_{\text{reg}}(3k)\gt\Phi_{\text{reg}}(3k+1)\gt\Phi_{\text{reg}}(3k+2)$, that is, the sequence decreases except that it increases from $3k-1$ to $3k$. Thus, a plausible candidate for a minimizing $3k$-gon is a degenerate one formed by a regular $(3k-1)$-gon with one vertex repeated. This is the weakest part of the argument; though numerically I haven't found any hexagons with lower ratios than this, I can't say that the random search has been efficient enough to exclude them.

Here are algebraic expressions for some values according to the guess:

$$\begin{array}{c|c} n&\Phi(n)\ \hline 4&\frac12\ 5&\frac1{\sqrt5}\ 6&\frac1{\sqrt5}\ 8&(2+\sqrt2)/8\ 9&(2+\sqrt2)/8\ 10&(2+\sqrt5)/10 \end{array}$$

-
Very nice. As you said, though, the $n = 3k$ is the weakest point, and Monte Carlo found the following coordinates (x1, y1, x2, y2 ... x6, y6): 0.589910783448771 0.011954420084427 0.734357166929861 0.110204431455905 0.658444901852673 0.259625291386871 0.609468376791231 0.292786131345568 0.436285745297418 0.308872355053235 0.391044861597499 0.142573905368672 giving max ratio of 0.446356873396086 < 1/ sqrt(5) = 0.447213595499958 It seems to be an affine-regular pentagon with one vertex split –  ivancho Dec 23 '11 at 19:51
@ivancho: Great, thanks! So the search continues... Is this already locally optimized, or just a random hit that could be further optimized? –  joriki Dec 24 '11 at 1:15
@ivancho: I'm thinking that if this really is (an affinely transformed version of) a regular pentagon with one vertex split, it may not generalize to higher $n$, since the gain from the split will decrease with increasing $n$. It may be possible to calculate up to which $n$ the ratio can be decreased by the split. –  joriki Dec 24 '11 at 4:03
@ivancho Excellent catch! –  Norbert Dec 24 '11 at 9:03
@joriki It's just a random hit - you may be able to tweak it further. I'll look into adding gradient descent to the search. You are right that vertex splitting won't generalize, but the extra degrees of freedom might still be important. –  ivancho Dec 24 '11 at 13:29