[請益] 超大集合中取符合規則的超小子集

[j100002ben (波卡Poka)]

標題下的很爛，可是我真的不知道要下什麼標題會比較好...



假設有一個矩形範圍（ex: 100cm*100cm），

裡面有非常多（ex:100000up）個隨機位置的圓形（ex:每個皆直徑10cm），

每一個圓形可能會和其他圓形相交/相割，

目標要找出矩形範圍內，最多不重疊的圓形

除了暴力解之外，我想不太出來我知道的演算法能夠處理這個問題

因為感覺像是排列組合（附帶檢查兩圓是否重疊）

一個矩形範圍不重複排滿頂多20-30個...

然後100000個就要檢查100000 * 99999 * ... * (100000-30)次

有沒有比較快速處理這種問題的方法？


比較是否重疊應該可以直接當成O(1)時間，

Ram夠大可以把全部的狀態放進去...

但是比較這麼多次也是很花時間的..


平行運算也有想過....

但是也要算法可以把資料切開來「平行」才行...

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.233.250
※ 編輯: j100002ben      來自: 118.168.233.250      (06/22 04:56)
推 EdisonX:比較那麼多次？
推 EdisonX:疑！是找最多「不重疊」，還是最多「不相切、相割」？
→ j100002ben:應該是說最多「互相]不相切也不相交的圓
→ j100002ben:差一個等號www
→ j100002ben:我說得比較那麼多次主要是說：先找一個，看看剩下符合
→ j100002ben:的在找一個，遞迴跑20-30層進去（迴圈也可以XD）
→ j100002ben:所以真的會跑很久....
推 fatalismo:座標為整數嗎？
推 LPH66:這問題可以轉換成 maximum independent set 問題
→ LPH66:感覺不太妙...
→ tkcn:greedy 要做出不錯結果應該不難，但要保證最佳解恐怕不容易
→ j100002ben:座標是整數，因為擔心精確度問題..
→ j100002ben:Greedy應該不行，不然可能會再某個角落停住..
推 bigpigbigpig:可以考慮先把這100000個點用x,y座標排序，先比x再比y
→ bigpigbigpig:這樣就只需要考慮一些小block附近的圓是否互相cover