[問題] 不重疊的圓求最大面積 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 就是你要的答案?

繼續閱讀