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.

  • 4
    $\begingroup$ 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. $\endgroup$ Sep 27, 2013 at 3:02
  • 1
    $\begingroup$ 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$? $\endgroup$ Sep 27, 2013 at 8:46
  • $\begingroup$ 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. $\endgroup$ Sep 27, 2013 at 9:46

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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