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

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

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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