[問題] 不重疊的圓求最大面積

[jjwang (jjwang)]

假設平面上有N個圓, 圓心的座標分別是(X1,Y1)~(Xn,Yn),
如果有以下限制:
1. 每個圓的半徑最大為MAX_R
2. 所有的圓都不可以重疊

想要求符合上述限制之下, 當N個圓的總面積為最大時, 每個圓的半徑(R1~Rn).

請問是否有演算法可以找出解呢?

google了一下沒有找到相關資料, 是否有類似的問題或者關鍵字可以協助找到參考資料?
謝謝


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.52.71
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1413991824.A.03F.html
推 pika0923: 問一下  覆蓋半徑為0的圓算重疊嗎?
to pika0923, 半徑0不算重疊, 所以如果只有兩個圓, 且兩個圓距離<2*MAX_R,
此時兩個圓總面積最大的時候可能為R1=0, R2=MAX_R.
謝謝

→ scwg: Quadratic programming: constraints 都是 Ri+Rj<=dist(i,j)
→ scwg: 總面積是 pi*sum Ri^2
to scwg, 謝謝提供關鍵字Quadratic programming, 我會往這個方向查看看.

推 DJWS: circle packing / 每個圓的半徑都是 MAX_R 就是你要的答案?
to DJWS, 如果兩個圓距離<2*MAX_R, 圓的半徑就不能是MAX_R, 不然會重疊.
謝謝提供circle packing關鍵字, 我會去査看看.

※ 編輯: jjwang (36.227.110.104), 10/24/2014 06:13:42