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?

Answer 1

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

Answer 2

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.

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.

Answer 4

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.