作者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/m.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