3
$\begingroup$

Given the dimension of a rectangle and the radii of n unequal circles, how can I decide if these circles can fit in the rectangle?

I don't know if there is a formula to compute such a thing!

The formula is straightforward if they are only two circles, not n circles. Also, it can be deducted if they are rectangles, not circles. But I can't figure it out for that case.

$\endgroup$
3
  • 1
    $\begingroup$ This is NP-hard, as well as for rectangles, you're unlikely going to find any formula $\endgroup$
    – fontanf
    Aug 7, 2023 at 6:14
  • $\begingroup$ If the circles all have distinct diameters, then you just have to check that the largest's circle diameter is less than the rectangle's width, and place all circles around the same centre. $\endgroup$
    – Stef
    Aug 7, 2023 at 13:47
  • $\begingroup$ @stef For circle packing, each pair of circles must have disjoint interiors. $\endgroup$
    – RobPratt
    Aug 7, 2023 at 15:25

1 Answer 1

6
$\begingroup$

You can determine whether such a packing is possible by solving a nonconvex quadratically constrained feasibility problem where the decision variables are the coordinates of the circle centers. See http://yetanothermathprogrammingconsultant.blogspot.com/2018/05/knapsack-packing-difficult-miqcp.html

$\endgroup$
1

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.