Consider a space of finite area (for eg., a rectangle). We need to pack circles of fixed radius in this finite area. Note that the position (coordinates) of every circle in space is given and fixed.

Two circles cannot be packed in the same rectangle if their areas overlap. Is there an algorithm with provable guarantees that minimizes the number of rectangles that we need to pack all the circles?

What is the best online variant of this algorithm? We can consider extensions of first fit, best fit, etc., to this problem. Are there any guarantees on their performance?


If I understand your problem statement correctly, the size of the rectangles does not matter, as you are basically just copies of the same rectangle, and all circles lie within that, right? So this becomes a purely combinatorial problem: some pairs of circles may be placed in the same rectangle, while others may not. This is an instance of the set cover problem.

As the problem is NP-hard, it is rather unlikely that a polynomial time algoritm does exist. On the other hand, an exponential algorithm with proven guarantees is easy: try all possible ways to form a set of non-empty sets from your circles, never putting two overlapping ones in the same set, and keep track of the minimal number of sets obtained. There might be solutions with slightly better performance for real-life applications. There should be ample literature on the issue.


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.