I want to cover a circle of radius $r$ with squares of side $l$. How can I find a good lower and upper bound for the number of squares $N(r,l)$ I need to use?
[Math] cover a circle with squares
geometry
Related Solutions
This is a disk covering problem. As you have stated it, it is not quite as difficult as some others.
The first task is to find the minimum number of small circles which cover the circumference of the bigger circle rather than the whole area. If this is $m$ then it will be impossible to have a regular $m$-gon with edges of length $2r$ fitting strictly inside the circle of radius $2r$. This implies $m \ge 6$.
It turns out to be just possible to cover the circumference of the bigger circle with 6 smaller circles, and ignoring symmetries there is only one way to do it (you get a regular hexagon whose vertices lie on the bigger circle and whose edges are diameters of the smaller circles). But this leaves an uncovered area in the middle, which needs at least one (and in fact exactly one) more.
So the answer is seven smaller circles.
Here's an $16$-approximation, assuming the object does not have holes. In particular, this approximation gives disjoint rectangles, and thus, is an instance of a Polygon Covering (nevertheless the bounds hold).
The union of the squares can be alternatively seen as a rectilinear polygon. We let the vertices of the polygon be the sharp points on the boundary of the polygon. Let $V$ be the number of such vertices. I will describe an approach based on the sweep-line triangulation algorithm. Basically, I will give a trivial triangulation if the polygon is monotone, and will later describe how to transform the polygon into monotone pieces.
If the polygon is monotone and does not have holes
First, let's consider what happens if the polygon is monotone (in $y$ coordinates) and have no holes. Let $P$ be the optimal number of rectangles to cover this polygon. First, I claim that
$$4P \le V$$
That is, $V$ is at most $4$ times the number of rectangles in the optimal answer. To see this, consider any rectangle covering the object. What is the maximum number of vertices this rectangle can touch? The answer is $4$ and thus, the bound follows.
Now, we can construct $V$ rectangles that cover everything as follows: Let $Y$ be the sorted list of distinct $y$ coordinates of the vertices of the polygon. For every pair of adjacent $y_i \in Y, y_{i+1} \in Y$, construct a rectangle to cover the polygon. Clearly this constructs at most $V$ rectangles.
Making the polygon monotone
We do a similar approach with triangulation: we make the polygon monotone and cover each monotone piece by rectangles. We can do monotonizing in a similar approach as in triangulation (alluded in the wiki): whenever we encounter a concave point that "faces down", we draw a line from the point left and right until we hit the boundaries of the polygon, and cut the polygon there, creating separate polygons in the process (it really is similar to the algorithm described in the wiki, but instead of connecting it to the vertex in the left/right sides of the polygon, we create a new vertex in the corresponding boundary). Thus, each "concave" point may create at most $2$ new vertices, and the $12$-approximation follows.
Now, how many concave points can a rectilinear polygon has? It is at most the number of convex points it have (in fact, it is exactly $4$ more than that). Now, if $V_x$ is the number of convex vertices of the polygon, using a similar reasoning as before, we have $4P \le V_x$, and thus, this is a $4 \times (1+3) = 16$-approx algorithm.
What if the polygon has holes?
The bounds on the optimal answer no longer holds, and thus, no guarantee is present even if we were to monotonize the polygon using the vertices of the holes.
Best Answer
You have a circle (disk) of radius $r$, and cover it with squares having edge length $l$. Since the scale does not matter, we can use their ratio $$\lambda = \frac{r}{l}$$ Essentially, the answer is exactly the same if we are covering a circle of radius $\lambda$ with unit squares.
We know that the unreachable minimum is when the $n$ squares cover exactly the same area as the circle, i.e. $$\bbox{n \gt \pi \lambda^2} \quad \iff \quad \bbox{N(\lambda) \ge \lceil \pi \lambda^2 \rceil} $$ where $\lceil\,\rceil$ denote the ceiling operation, rounding up to next higher integer. ($\lceil 1 \rceil = 1$, $\lceil 1.001 \rceil = 2$.)
The foolproof method would be to create a square with same size as the circle diameter, so $$\bbox{n \le (2 \lambda)^2} \quad \iff \quad \bbox{N(\lambda) \le \lceil 2 \lambda \rceil^2}$$
This gives us our initial bounds, $$\bbox[#ffffef, 1em]{ \lceil \pi \lambda^2 \rceil \le N(\lambda) \le \lceil 2 \lambda \rceil^2}$$ which isn't that bad, really.
We already know from Erich Friedman some interesting values of $N(\lambda)$ for small $\lambda$: $$\begin{array}{ll} N(\lambda) & \text{upper limit for } \lambda \\ \hline 1 & 0.5 \\ 2 & 2 - \sqrt{2} \approx 0.585 \\ 3 & \approx 0.794 \\ 4 & 1 \\ 5 & \approx 1.028 \\ 6 & \approx 1.126 \\ 7 & \approx 1.239 \\ 8 & \approx 1.375 \\ 9 & 1.5 \\ 10 & \approx 1.546 \\ 11 & \approx 1.608 \\ 12 & \approx 1.701 \\ 13 & \approx 1.779 \\ 14 & \approx 1.883 \\ 15 & \approx 1.991 \\ 16 & \approx 2.007 \\ 17 & \approx 2.042 \\ 18 & \approx 2.116 \\ \end{array}$$ Note that our upper bound for each $\lambda$ above is greater than the tabulated $N(\lambda)$.
If we look at what those solutions actually look like, it's clear that each one uses a different strategy, and constructing the cover is no trivial task.
So, there is not much we can do to get better bounds (more sensitive to small changes in $\lambda$) for small $\lambda$.
For larger lambda, we can get a tighter upper bound by selecting a method of constructing such a covering; in that case, we have "small" squares and a "large" circle.
One way would be to first cover a square the same size as the circular disk symmetrically, then remove the squares near the corners we know cannot be covering the disk.
Another way is to use a regular rectangular grid, where the circle is centered either at a grid intersection, or at a center of a cell, with each square covering exactly one cell, and count how many squares are needed in each row or column. This not only yields an exact answer, but the cover method is also quite clear. This is what I'll explore below.
We know that we can describe a circular arc of radius $r$ centered at origin spanning the positive quadrant ($x, y \ge 0$) using $$y = \sqrt{r^2 - x^2}$$ From the illustration above, we can see that the number of squares in each column (in the positive quadrant) is dictated by where the circle intersects the vertical grid line on the side closer to origin.
For the left case, we get $$\bbox[#ffffef, 1em]{N_0(\lambda) = 4 \sum_{i = 0}^{\lfloor\lambda\rfloor} \left\lceil \sqrt{\lambda^2 - i^2}\right\rceil}$$
For the right case, the bluish cross in the center has area $2 \lceil 2\lambda \rceil - 1$, and $$\bbox[#ffffef, 1em]{N_1(\lambda) = 2 \lceil 2 \lambda \rceil - 1 + 4 \sum_{i=1}^{\lfloor\lambda\rfloor} \left\lceil \sqrt{\lambda^2 - (i - 0.5)^2} - 0.5 \right\rceil}$$
These work for all $\lambda \gt 0$.
If we look at the results, we find that $N_0(\lambda)$ and $N_1(\lambda)$ are closer to the lower bound than the upper bound. Other than $N_0(\lambda) \lt N_1(\lambda)$ for $\lambda \in \mathbf{N}$ (i.e. $\lambda = \lfloor \lambda \rfloor$), and $N_1(\lambda) \lt N_0(\lambda)$ for $\lambda = \lfloor \lambda \rfloor + 0.5$, it is not obvious which one is better for any given $\lambda$.
The larger $\lambda$ gets, the closer $N_0(\lambda)$ and $N_1(\lambda)$ get to the minimum estimate. At $\lambda = 1000$, $\lceil\pi\lambda^2\rceil = 3141593$ and $N_0(\lambda) = 3145520$; only $0.125%$ of the squares total area is outside the circular disk.
If you don't want to calculate the two sums, you can always start from the definitions of $N_0(\lambda)$ and $N_1(\lambda)$, and create a (possibly piecewise) polynomial $f(\lambda)$ such that $f(\lambda) \ge \min( N_0(\lambda), N_1(\lambda) )$ for all $\lambda \gt 0$. I personally would use the numerical sums directly.