MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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.