Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 don't know for certain that any of the illustrated polygons are optimal. 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!

share|improve this question
    
Why do you keep writing $n{-}1$ instead of $n-1$? –  Michael Hardy Jan 29 '12 at 0:22
2  
@Michael: Just a precisionist controlling exact spacing. :-) –  Joseph O'Rourke Jan 29 '12 at 1:06

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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