圆形矩形的最大包装

Question

我在一个纳米技术实验室工作，我在那里做硅片切割。 （晶圆锯只切割平行线）当然，我们试图最大限度地提高我们切割的模具的产量。所有的模具都是相同的尺寸，不论是矩形还是方形，并且模具都是从圆形晶圆上切割下来的。基本上，我试图将最大的矩形打包成一个圆。

我只对MATLAB有一个非常基本的理解，并且对微积分有一个中等的理解。有没有（相对）简单的方法来做到这一点，还是我的方式在我的头上？

Answer 1

为了满足空间效率目标而将任意矩形包装成圆形是一般的非凸（NP-Hard）优化。这意味着没有优化或简单的解决方案可以最优解决这个问题。解决方法都将取决于您可以用来修剪搜索树或开发启发式的任何特定领域知识。如果您对这类问题没有经验，您应该咨询专家。

Answer 2

何去何从，和好运气：

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

，并得到这里：

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

至少你有一些想法你在这里解决。

Answer 3

这不像高斯的圈问题吗？见 http://mathworld.wolfram.com/GausssCircleProblem.html

或者，这可以被看作是一个“包装问题” http://en.wikipedia.org/wiki/Packing_problem#Squares_in_circle

Answer 4

我很惊讶的看了你的问题，因为我做了这个项目对我的训练作为一名数学教师。我也很高兴知道它被认为是一个NP问题，因为我的项目让我得出了同样的结论。

通过使用基本微积分，我计算了最大尺寸矩形的前几个'世代'，但它变得非常复杂。

你可以阅读我的项目在这里：

贝克特，R. 地块Pi的：曲线装箱问题。 Bath Spa MEC。 2009年

• Pages 1 - 15
• Pages 16 - 30

我希望我的一些研究结果是至少有趣的对你有用或。我认为这个想法的应用很可能是计算机纳米技术。

亲切的问候。