Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose you have a centrally symmetric convex 2D shape $C$ of area $A$, and you randomly throw down copies of $C$ on the plane so that each $C$-center lies within a given unit square $S$, until $S$ is entirely covered, i.e., every point of $S$ lies in some copy of $C$. For example, below (left) it took $9$ disks to cover the blue unit square, and (right) $10$ squares of the same area to cover the blue unit square (scaled differently):
Let $\rho(C)$ be the expected number of such randomly placed copies of $C$ needed to cover $S$. My questions are:

  • Q1. Is the disk the most efficient such covering shape, in that it minimizes $\rho(C)$ over all centrally symmetric convex bodies $C$ of the same area? If not, which shape is the best?

  • Q2. What shape is the worst covering shape, achieving the maximum of $\rho(C)$ over such shapes?

  • Q3. Do the best and worst shapes depend upon the choice to cover a square rather than to cover some other convex shape?

The same questions can be asked in any dimension.

share|improve this question
In your second example, shouldn't the centers of the pink squares lie inside the blue one? –  Eckhard Sep 26 '13 at 22:30
Oops, I accidentally shifted the corner rather than the center. Cannot fix now so I will delete until I can. Thanks! –  Joseph O'Rourke Sep 26 '13 at 22:34
Thanks, Eckhard, fixed now. –  Joseph O'Rourke Sep 27 '13 at 1:05
If you aren't bounding the diameter of $C$, then the space isn't compact, and there isn't a worst, since thinner and thinner rectangles do arbitrarily badly. –  Douglas Zare Sep 27 '13 at 3:02
Instead of worrying about fully covering $S$, is it not equivalent to think about the expected amount of $S$ covered by randomly placing a single copy of $C$? –  Benjamin Dickman Sep 27 '13 at 8:46
show 1 more comment

1 Answer

Q2: there is no worst shape, but arbitrarily bad shapes. Take a very thin and long rectangle: then any intersection of a displacement of it with the blue square has area bounded by some $a$, which can be made arbitrarily small. In consequence, at least $1/a$ copies are needed in any case to cover the blue square.

Variant of the question: search $C$ maximizing $\inf_A \rho(A\cdot C)$ where $A$ runs over linear maps.

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.