4
$\begingroup$

Let $O \subset \mathbb{R}^2$ be a convex open set of finite Lebesgue measure $1=m(O)$. Let's call a collection $P$ of $n$ disjoint open rectangles contained in $O$ a "partial cover of $n$ pieces". (The rectangles may be tilted.) Let us denote $C_n$ the collection of all $n$ piece partial covers of $O$. Write $$A_n = \sup_{P \in C_n} m(P).$$

Obviously, $A_n \to 1$ from below. From the convexity condition, it's also intuitively clear that convergence will be "good" - the intuition being that a convex set cannot differ by "too much" from a rectangle. Is it possible to make this intuition precise by writing a lower bound of some sort for $A_n$, perhaps depending on the diameter of $O$?

  • 0
    A circle is very different from a rectangle... what do you mean by "cannot differ by too much"?2011-07-25
  • 0
    You suggest a possibility yourself: could it be that eventually $A_n(O) \geq A_n(D)$, where $D$ is the circle of area $1$, for any $O$ satisfying the condition? (in other words, is the circle the "most difficult" of all convex shapes to cover with rectangles efficiently?)2011-07-25
  • 0
    You do have a trivial lower bound for $A_n$ using the diameter of $O$, since you can easily put a disk $D$ in your convex set $O$ such that $D$ and $O$ have the same diameter ; you can probably give lower bounds on $A_n$ in the circle which are not too complicated. I am not suggesting that the circle is the "most difficult" of all convex shapes.. but I suppose that convex shapes with small curvature are more easily covered by rectangles (i.e. the rectangles can cover a larger area for a fixed $n$) since the rectangles can get closer to the sides in that case.2011-07-25
  • 0
    If you mean "cannot differ by too much" as "cannot differ by more than the square differs from a circle", then yes, this is intuitive.2011-07-25

1 Answers 1

3

I can pull a lower bound for some subsequence of $A_n$. I start dividing the convex set in two parts and add one rectangle in each part. Then, considering the spaces not covered by the first two rectangle, these form $6$ disjoint convex subsets of the original sets, over which I apply one rectangle each : I am now left with $18$ convex subsets... and I keep tripling the number of convex subsets left, thus I am adding $ x_n \, \overset{def}{=} \, \, 2 + 2\cdot 3 + 2 \cdot 3^2 + ... + 2 \cdot 3^{n-1} = 2(3^n-1)/(3-1) = 3^n - 1 $ rectangles at each step of my algorithm (See drawings below). I claim that $A_{x_n} \ge a_n$ (and $a_n$ is also described below, and converges to $1$ at a reasonable speed).

Let $\mathrm{diam}(O)$ be the diameter of $O$ and let two points $x$ and $y$ on $\partial O$ such that $\| x - y \| = \mathrm{diam}(O)$. (The function which takes two points in $O$ and outputs their distance is continuous, and $\partial O$ is compact, so we indeed have such a couple $(x,y)$.) This means that at point $x$, the tangent parallel to $\partial O$ which goes through $x$ is orthogonal to the line that goes from $x$ to $y$. See drawing below.

enter image description here

Now since $x$ and $y$ are chosen so that their distance is maximal, the vectors tangent to $\partial O$ at $x$ and $y$, in both "up" and "down" directions (see drawings) are going to point inwards (because they have maximal distance), so that the "height" of points on $\partial O$ relatively to the $x-y$ axis will be a concave function (minus the function is convex), thus has a maximum. Choose the point $z_1$ which has maximum height for the top zone, and $z_2$ for the bottom zone. I have made another drawing which considers the bottom case, and the top case is symmetric.

In the drawing I am defining $f(t)$ to be the area of a certain rectangle. I define $f : (0,a) \to \mathbb R$ by letting $t$ be a distance from the intersection between the $x-y$ axis and the point dropped orthogonally from $z_2$ (which is the bottom point) and some point to the left of that point on the $x-y$ axis. To draw the rectangle, you drop down vertically, then turn orthogonally until you hit the boundary, and then turn orthogonally and stop at the $x-y$ axis again. I am defining the rectangle in this manner because the worst convex set that has $x$, $y$ and $z$ at those places is just two triangles, hence area will be at its minimum and I will derive a lower bound.

enter image description here

Using geometry, you can easily see that $$ f(t) = (t+\beta)(h-\alpha) = \left(t+\frac{t(d-a)}a \right)\left( h - \frac{ht}a \right) = \frac{dh}a \left( t \left( 1 - \frac ta \right) \right). $$ which gives the maximum at $t = \frac a2$ (natural, isn't it) and a maximum of $\frac{3}{16} dh.

Now the area of both rectangles is $\frac{3}{16}dh_1 +\frac{3}{16}dh_2 = \frac{3}{16}(d(h_1+h_2)) \ge \frac{3}{16}$ and the inequality comes from the fact that you can enclose your convex set in a box of width $d$ and height $h_1+h_2$ where $h_1$ is the maximal height of one of the constructions and $h_2$ is the other one.

At step $1$, I have removed at least $r=3/16$ of the set $O$ with 2 rectangles. The space left (imagine a circle with a square inscribed in it, there are $4$ zones left... these are the new convex sets I am iterating over). Now on the $(1-r)$ area left, I can remove at least $3/16$'s of it, hence there is $r + (1-r)r$ area removed now. Iterating in this manner, I obtain $$ a_1 = r, \qquad a_n = a_{n-1} + (1-a_{n-1})r $$ and since this sequence is clearly increasing and bounded above, it converges, and letting the limit $a = a + (1-a)r$, you find $a = 1$.

I think geometric convergence is "good enough". Don't you think?

Thanks to Theo Buehler for the hint on using screenshots.

  • 0
    Well the condition $m(O) = 1$ implies that $O$ is bounded.2011-07-25
  • 0
    After dividing $O$ using the line $xy$, you should divide each half again by dropping a perpendicular from the point farthest from $xy$. This gives you four pieces, each bounded by an right angle, and with nice tangents; my point is that now these can be subdivided into rectangles very naturally.2011-07-25
  • 0
    Also, I think the worst case here is a diamond or lozenge shape, not a circle. But in this case the area ratio is exactly 1/2, so your argument probably still works (apart from possibly a constant factor).2011-07-25
  • 0
    @Rahul : This is exactly what I've tried to describe, and by taking the worst case (where the point farthest from $xy$ is such that the convex set is, on this side, two triangles, with end points $x,y$ and the farthest point), I've derived the lower bound $3/16$. To make an argument that can iterate itself though, you can't just turn the rectangles around as you wished... it makes trouble.2011-07-25
  • 2
    I reiterate: if a convex set in $\mathbb{R}^{n}$ has measure one then it must be bounded. To see this, observe that it can't be contained in a hyperplane (else it would have measure zero), so it must contain $n+1$ points $y_0, \ldots, y_n$ in general position. If the set is undbounded then you can take a sequence $(x_k)$ tending to infinity and the convex hull of the points $y_i$ and $(x_k)$ will have infinite volume. Re hints: The graphics packages don't work here. The easiest way to do it is to do it on your machine and upload a screen shot.2011-07-25
  • 0
    I remember saying thanks somewhere for that remark ; I must have never posted it. Thanks "again" I guess. I knew sets of finite measure weren't necessarily bounded so that's why I supposed the set was bounded without thinking it had to be... but it's a very good remark.2011-07-25
  • 0
    How do I upload screenshots?2011-07-25
  • 0
    Hit 'ctrl+G' while editing or click on the photograph icon in the toolbar right above the editing field (rightmost icon in the second group). This allows you to upload a graphics file from your computer. By the way: Add an @Theo in front of your comments if you want me to be notified of your comments.2011-07-25
  • 0
    @Theo : Yeah... should've done that ; I usually do. =P Thanks again for the tip though.2011-07-25
  • 1
    THERE you go. Now I think my explanation is fine. =)2011-07-25
  • 0
    I like what you wrote. It's a little hand-wavy at parts, but so was my question, so I guess we're even. ;) Now can it be improved on?2011-07-25
  • 0
    One word : probably.2011-07-25