[問題] 不重疊的圓求最大面積
看板Prob_Solve (計算數學 Problem Solving)作者jjwang (jjwang)時間10年前 (2014/10/22 23:30)推噓2(2推 0噓 2→)留言4則, 3人參與討論串1/1
假設平面上有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
推
10/22 23:46, , 1F
10/22 23:46, 1F
to pika0923, 半徑0不算重疊, 所以如果只有兩個圓, 且兩個圓距離<2*MAX_R,
此時兩個圓總面積最大的時候可能為R1=0, R2=MAX_R.
謝謝
→
10/23 00:19, , 2F
10/23 00:19, 2F
→
10/23 00:19, , 3F
10/23 00:19, 3F
to scwg, 謝謝提供關鍵字Quadratic programming, 我會往這個方向查看看.
推
10/23 07:42, , 4F
10/23 07:42, 4F
to DJWS, 如果兩個圓距離<2*MAX_R, 圓的半徑就不能是MAX_R, 不然會重疊.
謝謝提供circle packing關鍵字, 我會去査看看.
※ 編輯: jjwang (36.227.110.104), 10/24/2014 06:13:42
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
