Bram Cohen's geometry question

gistfile1.txt

@bramcohen writes: "What's the maximum ratio between the volume of a
convex shape and the volume of the smallest right angle box it can fit
in?"

Considering the 2D case.

Limit attention without loss of generality to convex polygons.

When discussing rectangles, we use the following terminology:

               top edge
    +----------------------------------+
    |                                  |
    | left edge             right edge |
    |                                  |
    +----------------------------------+
              bottom edge

We say wolog that the top and bottom edges of a rectangle R are the
horizontal edges, and the left and right edges of R are the vertical
edges. We say that line segments are horizontal iff they are parallel
with the horizontal edges of R, and vertical iff they are parallel
with the vertical edges of R.

Definition: a *snug polygon* P of a rectangle R is a polygon
completely contained within R such that there is no other rectangle R'
with less surface area than R that could be oriented so as to
completely contain P.

Definition: a *minimal snug polygon* P of a rectangle R is a snug
polygon of R that has least (or least-equal, in general) surface area
of all snug polygons of R.

Lemma 0: all snug triangles of R have the same surface area.

  Proof: A snug triangle P of R must have all three vertices on the
  perimeter of R, because if any vertex of P were strictly within R,
  there would exist some R' smaller than R that could contain
  P. Furthermore, at least two vertices of P must be vertices of R,
  because otherwise there would exist an R' smaller than R that would
  contain P. (Need to flesh this out.)

Lemma 1: Let ABC be a triangle. Let D be a point along BC. Let X be a
point along BA. Then triangle DCX has surface area proportional
to |BX| / |BA|.

  Proof: surface area equation for triangles (area = half height times
  base).

Lemma 2: For every X not equal to B, a point X' can be found such that
the surface area of DCX' is less than the surface area of DCX.

  Proof: any X' between B and X can be chosen, because lemma 1 says
  that values of X closer to B have smaller surface area.

Hypothesis: no non-triangular minimal snug polygon of a rectangle R
has surface area smaller than a minimal snug triangle of R.

  Proof by contradiction: assume there is some non-triangular minimal
  snug polygon P of R that has less surface area than a snug triangle
  of R. There are two cases: either

    - a vertex V of P not lying on an edge of R exists, in which case
      a convex polygon P' exists having all the vertices of P except
      V. The surface area of P' is less than that of P, therefore P
      cannot be a minimal snug polygon; or,

    - no such vertex exists, in which case either

      - P is a triangle, ruled out by assumption, or

	  - let V be the vertex not on either the top or bottom edges
        of R furthest away from the bottom edge of R. (Wolog we
        restrict ourselves to considering the case where V is on the
        left edge of R.) Let A be the counterclockwise neighbouring
        vertex of V, and B be the clockwise neighbouring vertex of
        V. Then VAB is a triangle. There are two cases:

	    - Line AB is vertical. Then VAB is a snug triangle of the
          rectangle defined by the top, left and bottom edges of R and
          the line AB. By lemma 0, every point V' on the left edge of
          R gives a triangle V'AB with surface area equal to the
          surface area of VAB. Let A' be the counterclockwise
          neighbour of A. Choose such a point V' such that the line
          V'A is parallel to the line V'A'. Then the polygon P' having
          vertex V' instead of V, not having vertex A, and otherwise
          having the remaining vertices of P has surface area the same
          as that of P, one fewer edge than P, and is snug in R by
          construction (this is a bit shaky). Either P' is a triangle,
          yielding contradiction, or by induction (!! not well-formed)
          the whole process can be repeated from the beginning with P'
          instead of P.

        - Line AB is non-vertical. Then there exists some point C on
          the left edge of R where AB and the left edge of R
          intersect. By lemma 2 a point V' can be found such that the
          surface area of V'AB is less than the surface area of
          VAB. Of all such V', choose the one closest to C such that
          the polygon with all vertices of P but with V replaced by V'
          remains convex. Let the polygon P' have vertex V' instead of
          V, not have whichever of A or B no longer makes any
          contribution to the surface area of P', and otherwise have
          the remaining vertices of P. The surface area of P' is less
          than that of P because it contains triangle V'AB instead of
          VAB. P' is snug in R by construction (this is a bit
          shaky). Then either P' is a triangle, in which case
          contradiction, or by induction (!! not well-formed) we can
          repeat the whole process with P' instead of P.