I thought of a problem but have no idea how to solve it. The problem is as follows:

Given 2 numbers, n and r, find the side length (S) of the smallest square that encloses n circles each of radius r without any overlap among any of the circles.

enter image description here

I though about a greedy approach that would find the optimal position for each circle locally and placing it before moving onto the next one, but realized that it would be difficult without being given definitive positions of each of the circles. Is there a solution to this problem?


This is known as circle packing in a square. The Wikipedia article I link to has a citation to this webpage, which lists the best packings known for $n \le 10000$, and also has many references to papers that study this problem. I suggest studying them to see what methods they have used.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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