How can I packed equal circles with raduis R inside a rectangle L X W ??

Dear all I have a rectangle L X W (L=6,W=2), and n equal circles with radius = R, How can I packed max number of non-overlapped circles inside this rectangle Thanks

[Stephen23]

@Ahmad Hani: just because a question is simple does not mean that that answer is correspondingly simple. There is no general solution to this problem, no matter how trivial it might seem to a human.

https://math.stackexchange.com/questions/701/how-many-circles-of-a-given-radius-can-be-packed-into-a-given-rectangular-box

<ftp://ftp.math.ethz.ch/EMIS/journals/HOA/AOR/Volume2009/150624.pdf>

etc, etc.

You might find some heuristic or special case that resolves your task. Do some reading!

[Ahmad Hani]

Thanks sir but where can I find the proof for NP hard?

[Stephen23]

"where can I find the proof for NP hard?"

As far as I am aware:

• there is no general algorithm to solve this problem.
• there is no general way to check if the solution is correct.

[Jan]

@Stephen Cobeldick: Please copy your comment to the section for answers, such that it can be accepted.

[Ahmad Hani]

 Accepted Answer
Thanks @Stephen Cobeldick

Answer 1

[Jan]

See e.g. https://en.wikipedia.org/wiki/Circle_packing_in_a_square : As Stephen has said already, the problem is hard. You cannot expect a general solution in the forum.

[Ahmad Hani]

Where can I find the proof for NP hard?

[Jan]

@Ahmad Hani: You can search in the net exactly as the forum's members can. Note that "proof for NP hard" is not clear or unique, so you need more information to find, what you want.

[Walter Roberson]

https://arxiv.org/abs/1008.1224 " Circle Packing for Origami Design Is Hard", Erik D. Demaine, Sandor P. Fekete, Robert J. Lang

"We show that deciding whether a given set of circles can be packed into a rectangle, an equilateral triangle, or a unit square are NP-hard problems"