[问题] 不重叠的圆求最大面积 jjwang PTT批踢踢实业坊

[问题] 不重叠的圆求最大面积

楼主: jjwang (jjwang) 2014-10-22 23:30:21

假设平面上有N个圆, 圆心的座标分别是(X1,Y1)~(Xn,Yn),
如果有以下限制:
1. 每个圆的半径最大为MAX_R
2. 所有的圆都不可以重叠
想要求符合上述限制之下, 当N个圆的总面积为最大时, 每个圆的半径(R1~Rn).
请问是否有算法可以找出解呢?
google了一下没有找到相关资料, 是否有类似的问题或者关键字可以协助找到参考资料?
谢谢

作者: pika0923 (宜安) 2014-10-22 23:46:00

问一下覆蓋半径为0的圆算重叠吗?

作者: scwg ( ) 2014-10-23 00:19:00

Quadratic programming: constraints 都是 Ri+Rj<=dist(i,j)总面积是 pi*sum Ri^2

作者: DJWS (...) 2014-10-23 07:42:00

circle packing / 每个圆的半径都是 MAX_R 就是你要的答案?

继续阅读