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

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 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.