2
$\begingroup$

I have a square 800x800 and i need to fully cover it with the least number of circles possible, each circle has a radius of 150.

QUESTIONS: - What pattern would be the best to use? Clover, diamon or something different? - How should i dispose the circles, and how many of them are needed? - Is there a relation to the data above and the number of circles?

$\endgroup$
0

4 Answers 4

Reset to default
3
$\begingroup$

Based on my code written for this answer on puzzling.se I found a solution with 14 circles:

Coordinates:

 0, 278.94802, 266.51974
 1, 494.65958, 668.05464
 2, 278.26437,   2.45011
 3, 681.45341, 711.12797
 4, 494.75679, 131.85939
 5, 701.33277, 289.36821
 6,  65.60149, 400.01636
 7, 487.09331, 399.91577
 8, 278.98163, 533.39755
 9,  64.97167, 666.56928
10,  64.93806, 133.44708
11, 701.27443, 511.03548
12, 681.50238,  89.15878
13, 278.33274, 797.62037
$\endgroup$
1
2
$\begingroup$

This is not an answer but some partial findings.

As shown in the figure at end, 15 circles are enough to cover the square.

To construct the covering, you first place 4 circles centered on the diagonal. These are the 4 red circles in the figure. Let look the red circle centered at $A$ in the figure. Let's say its boundary intersect an edge of the square at $E$. Let $F$ be the mid-point on that edge. Construct a circle centered at $E$ with radius 300 and let it intersect the perpendicular bisector of the edge at $R$. If one construct a circle passing through $E, F$ and $R$. You obtain one of the green circles in the figure. Replicate it by symmetry, you get 8 green circles. Together with the 4 red circles, these 12 circles covered the edges of the square and left with a hole in the middle. From the figure, one can see that one can cover the hole with 3 circles.

Notice the hole is nearly filled by a single circle. It might be possible to reduce the number by 1 but I can't figure out how to do that.

Cover a square with 15 circles

$\endgroup$
5
  • $\begingroup$ this soli ti in ma mes an ideal octagon in The middle; what id re instead cover the edges using the radius of the circles? $\endgroup$
    – elnath78
    Commented Nov 9, 2013 at 16:06
  • $\begingroup$ @elnath78, the centers of the 8 green circles doesn't form a regular octagon. If you move them around to make a regular octagon, the hole in the middle becomes smaller in the diagonal but bigger in the horizontal/vertical directions. As a whole, that didn't help. About covering the edges with radii of circles, one can show that it need 10 circles for the job. When I cover the edges with 10 circles, the hole in the middle getting bigger. I now need 5 instead of 3 circles to cover the hole. Since that configuration is harder to describe, I don't include that in my answer. $\endgroup$
    – achille hui
    Commented Nov 9, 2013 at 16:37
  • $\begingroup$ I think it can be reduced by 1 shifting one blue circle to the edge of green circle intersection and then placing the other, but im not sure about it with this circle/sqare size. $\endgroup$
    – elnath78
    Commented Nov 11, 2013 at 9:21
  • $\begingroup$ @elnath78 I'm working on the opposite direction. I try to bound the required number of circles from below. Hopefully, that will give us get an idea what the minimum configuration looks like. I think I have a proof that we need at least 13 circles. I'm still struggling to push the lower bound to 14. $\endgroup$
    – achille hui
    Commented Nov 11, 2013 at 10:05
  • $\begingroup$ it would be interesting to also calculate the coordinates of each circle center. But i have a different question: the solution with least used circles would also be the solution with least shared area (overlapped) or not necessarily? $\endgroup$
    – elnath78
    Commented Nov 12, 2013 at 11:31
1
$\begingroup$

The following site has diagrams for $1$ to $12$ circles. Unfortunately, it stops when the square side is just less than five times the circle radius.

https://erich-friedman.github.io/packing/circovsqu/

Sixteen circles ranged in a regular, square pattern $200$ apart, at $(100,100),(100,300)$ and so on will cover the $800$ square.

$\endgroup$
1
$\begingroup$

For the following arrangement of $11$ points, the minimum distance (indicated by the blue line segment) between pairs is $>300$, implying a lower bound of $11$ circles: enter image description here

I obtained the following approximate solution with $14$ circles by randomly generating $10000$ points and solving the corresponding set cover problem. There are still some gaps, but maybe it can be tweaked to cover them:

enter image description here

$\endgroup$
3
  • $\begingroup$ @2012rcampion maybe you can apply your approach from puzzling.stackexchange.com/questions/110592/… $\endgroup$
    – RobPratt
    Commented Nov 10, 2021 at 23:15
  • $\begingroup$ Yep, just upvoted! $\endgroup$
    – RobPratt
    Commented Nov 13, 2021 at 2:55
  • $\begingroup$ You can improve the lower bound withn an arrangement of 12 points with a distance of 310.98 (see here) $\endgroup$
    – 2012rcampion
    Commented Nov 13, 2021 at 6:44

You must log in to answer this question.

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