# The largest rectangle in a stair case polygon with n vertices

Let's define a stair case polygon to be a polygon look like the following.

Let the lower left most point to be the origin, all edges are axis-aligned.

One can see if we remove a stair case polygon from a rectangle, we get another stair case polygon.

Let $S_k$ be some $k$ vertices stair case polygon. Let $A(x)$ be the area of the polygon x. Let $R_k$ be the largest axis-aligned rectangle that is contained in $S_k$

What can we say about the lower bound of $\frac{A(R_k)}{A(S_k)}$?

Currently I know $\frac{A(R_k)}{A(S_k)} \geq \frac{1}{(k-4)/2 + 1}$

Define the maximal rectangle as a rectangle that can't be stretched in any direction without going outside the polygon. There are only $(k-4)/2 + 1$ maximal rectangles, the union covers the entire polygon. Then at least one have area $\geq \frac{1}{(k-4)/2 + 1}$

I wonder does there exist a better lower bound? Or can we prove that's the best possible?

Motivation, I originally had a conjecture, that for any bounded continuous monotonic decreasing convex function defined in $[0,a]$ as $f(x)$. The maximal $xf(x)$ over the area under $f(x)$ is a constant. It turns out to be false, counterexample $f(x) = 1/x$. So now I'm doing this for a discrete version, the maximal $xf_k(x)$ over the area under $f_k(x)$ is a function of $k$, where $f_k(x)$ is the average value of $f(x)$ in each of the $k$ partitions of $[0,a]$.

-
I think at some vertices you need to make 90 degrees left turns also, no? – Willie Wong Feb 2 '11 at 15:46
Also, what is $x$ in your expression $\frac{1}{(x-4)/2 +1}$? Is that supposed to be $k$? – Willie Wong Feb 2 '11 at 15:48
Thanks, it's now fixed. – Chao Xu Feb 2 '11 at 15:56

## 1 Answer

I claim the estimate you have is sharp, but not attained.

That it is not attained is clear, since a decomposition by maximal polygons will always have some overlap.

To show that it is sharp, consider the following construction. Let $k$ be fixed. Let $1 > \epsilon > 0$ be a small positive number. Start with the unit square ($1\times 1$). Add to it the following maximal polygons, one at a time: $\epsilon^j \times \epsilon^{-j}$ for each $0 < j < (k-4)/2 + 1$. So each maximal polygon has area 1.

Each additional maximal polygon adds an area of $\epsilon^j \times (\epsilon^{-j} - \epsilon^{-(j-1)}) = 1 - \epsilon$ (the amount it protrudes from what is already there).

So the total area $A(S_k)$ for this figure is $\frac{k-4}{2}(1-\epsilon) + 1$. By choosing $\epsilon$ as small as you want you can make $A(R_k)/A(S_k) = \left((k-4)(1-\epsilon)/2 + 1\right)^{-1}$ as close to the bound you derived as possible.

-