15
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • $\begingroup$ Why do you keep writing $n{-}1$ instead of $n-1$? $\endgroup$
    – Michael Hardy
    Commented Jan 29, 2012 at 0:22
  • 3
    $\begingroup$ @Michael: Just a precisionist controlling exact spacing. :-) $\endgroup$
    – Joseph O'Rourke
    Commented Jan 29, 2012 at 1:06
  • 1
    $\begingroup$ The special case with all regular polygons would be interesting too — for that case finding the areas would boil down to finding the points of contact. $\endgroup$
    – user44143
    Commented Sep 9, 2022 at 13:20

1 Answer 1

Reset to default
2
$\begingroup$

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)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .