Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

enter image description here

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

share|improve this question
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
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer


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.