As a discrete analog of the MO question, "Löwner-John Ellipsoid: incribed and circumscribed," I've been wondering what might be the maximum ratio of this quantity? Let $P$ be a convex polygon of $n$ vertices, $P^+$ be a minimum area polygon of $n{-}1$ vertices circumscribing $P$, and $P^-$ a maximum area polygon of $n{-}1$ vertices inscribed in $P$.

Over all polygons $P$ of $n$ vertices, what is the maximum of the ratio area$(P^+)/$area$(P^-)$, as a function of $n \ge 4$?

Here are possible optimal (en/in)closures for a square and a regular pentagon:

      Nested Polygons
[Some updates below.]

I believe that it is known that the circumscribing $(n{-}1)$-gon must have one edge "flush" with $P$ (i.e., including an edge of $P$ as a subset), and that this may be proved in a 1984 paper by Chang and Yap "A polynomial solution for potato-peeling problem" (Discrete & Computational Geometry Volume 1, Number 1, 155-182), which I cannot access at the moment. This is certainly true for enclosing triangles. I am not sure if there is any analogous characterization of inscribed $(n{-}1)$-gons. A key result for minimum area circumscribing is by Victor Klee in 1986: "Facet-centroids and volume minimization," Studia Scientiarum Mathematicarum Hungarica, Vol. 21, 143-147, 1986. As the title indicates, he proved that each facet's centroid must touch $P$ (in any dimension). The circumscribing polygons I drew above have their edge midpoints touching $P$.

For $n{=}4$, $a \times b$ rectangles have an area ratio of $(2 a b) / (a b / 2) = 4$, illustrated with the square above; perhaps this is the worst ratio over all $n$?

Any ideas would be appreciated, from a clean proof (or counterexample!) that one circumcribing edge must be flush, to any constraints on the inscribed polygons, to an answer to the ratio question, even for specific $n$, even for regular $n$-gons. Thanks!

  • $\begingroup$ Why do you keep writing $n{-}1$ instead of $n-1$? $\endgroup$ – Michael Hardy Jan 29 '12 at 0:22
  • 3
    $\begingroup$ @Michael: Just a precisionist controlling exact spacing. :-) $\endgroup$ – Joseph O'Rourke Jan 29 '12 at 1:06

Just a note about inscribed polygons. It is easy to show that area$(P^-)\ge$ area$(P)(1-1/(n-2))$. This follows from the fact that among the triangles formed by three vertices of $P$, (at least) one with minimum area must ``lie'' on a side of $P$. (Proof: Take minimum area triangle, use area$\cdot 2=$ height$\cdot$base and move vertices.) Now triangulate $P$ such that this minimum area triangle appears. Omitting it we get a polygon with $n-1$ vertices, done. This bound is also sharp for regular $n$-gons. (Proof is again by moving the vertices of maximum area $(n-1)$-gon.

I guess the next task is to determine the minimum of area$(P^+)/$area$(P)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.