作者jjwang (jjwang)
看板Prob_Solve
标题[问题] 不重叠的圆求最大面积
时间Wed Oct 22 23:30:21 2014
假设平面上有N个圆, 圆心的座标分别是(X1,Y1)~(Xn,Yn),
如果有以下限制:
1. 每个圆的半径最大为MAX_R
2. 所有的圆都不可以重叠
想要求符合上述限制之下, 当N个圆的总面积为最大时, 每个圆的半径(R1~Rn).
请问是否有演算法可以找出解呢?
google了一下没有找到相关资料, 是否有类似的问题或者关键字可以协助找到参考资料?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.224.52.71
※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1413991824.A.03F.html
1F：推 pika0923: 问一下 覆盖半径为0的圆算重叠吗? 10/22 23:46
to pika0923, 半径0不算重叠, 所以如果只有两个圆, 且两个圆距离<2*MAX_R,
此时两个圆总面积最大的时候可能为R1=0, R2=MAX_R.
谢谢
2F：→ scwg: Quadratic programming: constraints 都是 Ri+Rj<=dist(i,j) 10/23 00:19
3F：→ scwg: 总面积是 pi*sum Ri^2 10/23 00:19
to scwg, 谢谢提供关键字Quadratic programming, 我会往这个方向查看看.
4F：推 DJWS: circle packing / 每个圆的半径都是 MAX_R 就是你要的答案? 10/23 07:42
to DJWS, 如果两个圆距离<2*MAX_R, 圆的半径就不能是MAX_R, 不然会重叠.
谢谢提供circle packing关键字, 我会去査看看.
※ 编辑: jjwang (36.227.110.104), 10/24/2014 06:13:42