# Covering a circle with rectangles

I have to solve this problem: cover a unit circle with a set of rectangles, expressed in terms of their centers and semi-axes, that do not overlap with each other.

The size (i.e. the semi-axes lenght) of the rectangles can change.

My desire is to keep the number of rectangles as low as possible. So far I have in hand a simple solution based on squares: I start with the circumscribed square and then, for each one of the four corners, I do the following:

1. Inside the surplus area, I remove the biggest square that can be inscribed. This operation splits the surplus area in two new surplus regions;
2. Inside each one of the new two surplus regions I remove the biggest square that can be inscribed. Once again the surplus regions are splitted in two parts.
3. I repeat the process a fixed number of times.

I would like to know if there is a more "efficient" way to solve my problem. By "efficient" I mean that, given a desired covering error, the solution keeps the number of rectangles as low as possible.

EDIT

In order to clarify my problem, I try to make this post more formal.

Lets consider a set of non-overlapping rectangles $$\begin{equation*} \mathcal{R}\triangleq \{R_i=(a_i, b_i, m_i)\}_{i=1}^N \end{equation*}$$ where $$a_i, b_i \in \mathbb{R}$$ are the semi-axes, $$m_i\in\mathbb{R}^2$$ is a vector containing the Cartesian coordinates of the center. The total area covered by the partition $$\mathcal{R}$$ is $$\begin{equation*}A_{\mathcal{R}}=4\sum_{i=1}^N a_i b_i\end{equation*}$$ because, by definition, the rectangles don't overlap with each other.

We can define the covering error as $$\begin{equation*} e_{\mathcal{R}}\triangleq \pi-A_{\mathcal{R}} \end{equation*}$$ which quantifies the quality of the current partition $$\mathcal{R}$$.

If the error is positive, then the partition is not covering some spots of the circle, if the error is negative then the partition is covering some spots that are not occupied by the circle.

My objective is get a partition that gives an error near zero, but I cannot use an infinite number of rectangles. Let's say we have a budget of $$N$$ rectangles, then I want to solve the following optimization problem \begin{equation*} \min_{\mathcal{R}} \left|\pi-4\sum_{i=1}^N a_i b_i\right|\\ \text{s.t. } \begin{aligned} |\mathcal{R}|&=N\\ R_i \cap R_j&=\varnothing \qquad i\neq j \end{aligned} \end{equation*} where $$|\mathcal{R}|$$ is the cardinality of the partition $$\mathcal{R}$$. In addition, I clarify once again that the elements $$R_i\in\mathcal{R}$$ are rectangles with center $$m$$, semi-axes $$a_i$$, $$b_i$$, so that $$\begin{equation*} R_i = [-a, a]\times [-b, b] \end{equation*}$$ moreover, as you can see from the formula above, the rectangles are aligned with the reference axis (i.e. they are horizontal or vertical).

EDIT 2.0

I want to clarify that I know that the packing problem is hard, and so I'm not expecting an optimal solution. I'm just searching for a "good solution", and by "good" I mean that, given the budget $$N$$, the "good solution" produces a cost that is smaller than the one produced by the solution that I've presented above.

• If as you said the size of the rectangle can change, then you only need one rectangle to cover it. Maybe you can upload a picture to describe what you want to do. Commented May 12, 2023 at 20:52
• Post edit: is that really your error function? We can make it $0$ with one rectangle. It won't be a good cover in any usual sense. Indeed, the way you have written it, it might miss the circle entirely. Just take $a=\pi, b=\frac 14$. I expect you meant to try to minimize the sum of the area of the excess region covered plus the area of the area in the circle which you miss. Something like that anyway. Maybe you want to allow those two errors to cancel, but I'd be surprised.
– lulu
Commented May 12, 2023 at 21:25
• Yes, of course you are right. I have to find a better definition of my problem. Commented May 12, 2023 at 21:30
• Try what I suggested. See if it does what you had in mind.
– lulu
Commented May 12, 2023 at 21:41
• You appear to be tacitly assuming that the rectangles' axes are parallel to the x- and y-axes of the plane. Is that right? Commented May 12, 2023 at 23:12