1
$\begingroup$

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.

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$
    – MathFail
    Commented May 12, 2023 at 20:52
  • 2
    $\begingroup$ 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. $\endgroup$
    – lulu
    Commented May 12, 2023 at 21:25
  • $\begingroup$ Yes, of course you are right. I have to find a better definition of my problem. $\endgroup$
    – matteogost
    Commented May 12, 2023 at 21:30
  • 1
    $\begingroup$ Try what I suggested. See if it does what you had in mind. $\endgroup$
    – lulu
    Commented May 12, 2023 at 21:41
  • 1
    $\begingroup$ You appear to be tacitly assuming that the rectangles' axes are parallel to the x- and y-axes of the plane. Is that right? $\endgroup$
    – Dan Asimov
    Commented May 12, 2023 at 23:12

1 Answer 1

1
$\begingroup$

Post isn't clear but here's what I got: Start with a circumscribed square around the unit circle.

Divide each side of the square into smaller segments to form a grid. The size of the segments will depend on the desired covering error and the resolution you want to achieve.

For each grid segment, calculate the distance from its center to the center of the unit circle. If this distance is less than or equal to the radius of the unit circle, consider this segment fully covered.

If the distance is greater than the radius, consider this segment as part of the surplus area. Place an ellipse with its center at the center of the grid segment and adjust the semi-axes of the ellipse to fit within the surplus region while touching the unit circle.

Repeat steps 3 and 4 for all grid segments, ensuring that the ellipses do not overlap with each other.

$\endgroup$

You must log in to answer this question.

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