6
$\begingroup$

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):
DisksSquares
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.

Improve this question
$\endgroup$
3
  • 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$
    – Douglas Zare
    Commented 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$
    – Benjamin Dickman
    Commented 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$
    – Joseph O'Rourke
    Commented Sep 27, 2013 at 9:46

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .