

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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|cite|improve this question
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
Thanks, Douglas and Benoît re Q2 and arbitrarily bad rectangles---that is clear. Benjamin, that equivalence is superficially plausible, but I don't see a supporting justification. – Joseph O'Rourke Sep 27 '13 at 9:46

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|cite|improve this answer

Your Answer


