Maximum packing of rectangles in a circle

Question

I work at a nanotech lab where I do silicon wafer dicing. (The wafer saw cuts only parallel lines) We are, of course, trying to maximize the yield of the die we cut. All the of die will be equal size, either rectangular or square, and the die are all cut from a circular wafer. Essentially, I am trying to pack maximum rectangles into a circle.

I have only a pretty basic understanding of MATLAB and an intermediate understanding of calculus. Is there any (relatively) simple way to do this, or am I way over my head?

Disappointment

Apart from the matlab syntax, you might want to also consider math.stackexchange.com and mathoverflow.net for solving the calculus part of the problem. – Guitarist

I'm not sure exactly what your question is. But the efficiency of packing of square/rectangles into a circle approaches 100% as the size of the square/rectangle approaches zero. – Karli

seems like interesting flavor of a knapsack problem en.wikipedia.org/wiki/Knapsack_problem – Asmodeus

As I understand it, he has rectangles (all of fixed size) which he is trying to pack in to a circle, also of fixed size. If the rectangle sizes were all differing, this would probably be an NP problem. But since they are all the same, this may actually be doable. – Bodleian

Answer 1

Go from here, and good luck:

http://en.wikipedia.org/wiki/Knapsack_problem

and get here:

http://www-sop.inria.fr/mascotte/WorkshopScheduling/2Dpacking.pdf

At least you'll have some idea what are you tackling here.

Chafe

Answer 2

I was fascinated to read your question because I did a project on this for my training as a Mathematics Teacher. I'm also quite pleased to know that it's thought to be an NP-problem, because my project was leading me to the same conclusion.

By use of basic calculus, I calculated the first few 'generations' of rectangles of maximum size, but it gets complex quite quickly.

You can read my project here:

Beckett, R. Parcels of Pi: A curve-packing problem. Bath Spa MEC. 2009.

• Pages 1 - 15
• Pages 16 - 30

I hope that some of my findings are useful to you or at least interesting. I thought that the application of this idea would most likely be in computer nano technology.

Kind regards.

Redden

Answer 3

Packing arbitrary rectangles into a circle to meet a space efficiency objective is a non-convex (NP-Hard) optimization in general. This means there will be no elegant or simple solution that will solve this problem optimally. The solution methods are all going to depend on any specific domain knowledge you can use to prune the search tree or develop heuristics. If you have no experience in this type of problem you should probably consult with an expert.

Vere

OP says "All the of die will be equal size, either rectangular or square". Not so NP-hard after all. – Preposterous

Answer 4

doesn't this resemble the Gauss's Circle Problem? See http://mathworld.wolfram.com/GausssCircleProblem.html

or, this can be seen as a "packaging problem" http://en.wikipedia.org/wiki/Packing_problem#Squares_in_circle

Gambrel