Covering a rectangle with circles

586 Views Asked by At

On a rectangle table with area A, n unit-radius circles are placed and it is not possible to place any extra circles without overlapping with some of the existing ones or without placing circle's center outside the rectangle which results in falling off of the table.

Notice that this placement and the number n are not unique for a given rectangle, but n, the rectangle, and the placement are given to us. Show that with 4n of these circles you can cover the rectangle entirely (that is any arbitrary point is covered by at least one circle).

1

There are 1 best solutions below

1
On BEST ANSWER

WOLOG, choose the coordinate system so that the table cover the rectangle $$R = [0,w] \times [0,h]\quad\text{ with }A = wh.$$ Let $C = \{ \vec{c}_1, \vec{c}_2, \ldots, \vec{c}_n \}$ be the centers of the $n$ circles. For any $\vec{x} \in R$, let $$d_C(\vec{x}) = \min\{ d(\vec{x},\vec{c}) : \vec{c} \in C\}$$ be the minimal distance of $\vec{x}$ to the centers. It is clear if there is a $\vec{x} \in R$ with $d_X(\vec{x}) > 2$, then the unit circle centered at $\vec{x}$ will not intersect any of the $n$ circles. This violates the condition we cannot add one more circles to the $n$ circles without overlapping. As a result, we have

$$\sup\{ d_C(\vec{x}) : \vec{x} \in R \} \le 2$$ Equivalently, we can cover $R$ by $n$ circles centered at $\vec{c}_i \in C$ with radius $2$. Scale everything down linearly by a factor of $2$, we can cover

$$\frac12 R \stackrel{def}{=} \left\{ \frac12\vec{x} : \vec{x} \in R \right\}$$ by $n$ unit circles centered at $\frac12\vec{c}_i$ with $\vec{c}_i \in C$. Tiling this configuration in both $x$ and $y$ directions once, we can cover $R$ by $4n$ unit circles centered at

$$\frac12 \vec{c}_i + \vec{d}_j \quad\text{ where }\quad \vec{c}_i \in C\quad\text{ and } \vec{d}_j = \begin{cases} (0,0),& j = 0\\ \left(\frac{w}{2}, 0\right),& j = 1\\ \left(0, \frac{h}{2}\right),& j = 2\\ \left(\frac{w}{2}, \frac{h}{2}\right),& j = 3. \end{cases}$$