18
$\begingroup$

I have a square with length of side is $a$. How to draw a number of circles inscribed in a square so that the sum of the radii of the circle is greatest? In the below picture is six circles inscribed in a square. We can consider number of circles are 5, 6, ... We consider number of the circles is fixed.

enter image description here

I am sorry, I don't know how to start.

PS. Another style I see www.packomania.com

I see this question at https://www.mapleprimes.com. With n = 14, n= 15 I compare between Mathematica and Maple.

enter image description here

enter image description here

enter image description here

There are differences between the two programs.

$\endgroup$
3
  • $\begingroup$ Do you restrict the number of circles ? Otherwise, you can fill-in many small circles in the cracks. $\endgroup$
    – A. Kato
    Commented Jun 18 at 1:24
  • $\begingroup$ Umm.... why not the limit of an infinite number of very small circles? $\endgroup$ Commented Jun 18 at 1:36
  • $\begingroup$ @DavidG.Stork Yes. Number of circles can be 5, 6, ... $\endgroup$ Commented Jun 18 at 1:40

1 Answer 1

20
$\begingroup$
  • We only test n=5,n=6.
  • We need three varaibles {x[i],y[i],r[i]} to determint a circle.
  • Set RegionWithin[reg, Disk[{x[i], y[i]}, r[i]]], {i, 1, n}] to ensure that the Disk contain in reg=Rectangle[].
  • {x[i], y[i]}, {x[j], y[j]}] >= r[i] + r[j] ensure that the Disks are disjoined.
Clear["Global`*"];
reg = Rectangle[];
n = 5;
sol = NMaximize[{Sum[r[i], {i, 1, n}], 
   Table[RegionWithin[reg, Disk[{x[i], y[i]}, r[i]]], {i, 1, n}], 
   Table[EuclideanDistance[{x[i], y[i]}, {x[j], y[j]}] >= 
     r[i] + r[j], {i, n}, {j, i - 1}], 
   Table[r[i] > 0, {i, 1, n}]}, 
  Table[{x[i], y[i], r[i]}, {i, 1, n}] // Flatten, 
  Method -> "SimulatedAnnealing"]

enter image description here

Graphics[{EdgeForm[Cyan], FaceForm[], 
  Rectangle[], {FaceForm[Red], 
    Table[Disk[{x[i], y[i]}, r[i]], {i, n}]} /. sol[[2]]}]

enter image description here

  • The cases n=6. enter image description here
$\endgroup$
5
  • 1
    $\begingroup$ Very nice, but results are suboptimal if n=19, 20, 21, 22, and I assume also for many other larger values. For some reason, such results contain a cluster of smallish circles at or near the lower left corner, together with a vacant area elsewhere that will easily accommodate a larger circle than one of the small ones which could be removed. $\endgroup$ Commented Jun 19 at 23:47
  • $\begingroup$ There is a tendency for ∑r to increase with n. This often fails; n=17 gives a lower value than n=16; clearly n=16's ∑r could be increased by adding a small circle in any interstice, thus giving a higher value than the algorithm gives for n=17. I suspect either NMaximize has a bug, or it is being misused. $\endgroup$ Commented Jun 20 at 3:05
  • 4
    $\begingroup$ @JamesStein, it's not a bug. If you look at the documentation for NMaximize, there are methods which are guaranteed to give a global maximum (Convex, MOSEK, Gurobi ...). However, SimulatedAnnealing is a heuristic method, so there is no guarantee you will actually reach the global maximum. $\endgroup$
    – Domen
    Commented Jun 20 at 9:50
  • $\begingroup$ @cvgmt Can I ask if it is possible to expand the answer to 3D?(I replaced with Ball and Cuboid but did not succeed) $\endgroup$
    – metroidman
    Commented Jun 22 at 3:19
  • $\begingroup$ @metroidman You can ask a new question. I don't test the case of 3D before. $\endgroup$
    – cvgmt
    Commented Jun 22 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.