4
我正在CUDA中實施凸包的分而治之的方法。這是我的方法： 自上而下：gpu中的平行凸包算法
- 創建列表以存儲凸包;
curSize =輸入大小（所有點）;
對於i：1至日誌N
- 開始
- curSize = curSize/2;
- 以每2個相鄰的凸殼中列表的列表，並將它們 合併成更大的船體（使用標準的上部和下部共同切線爲鴻溝&治凸包 方法）在curSize線程
- //最初，它合併每2然後在下一次迭代中使用 ，它將大小爲2的凸包合併成更大的 凸包等。最後，列表的列表將包含一個 船體上的單點列表
- 結束
但它變得太複雜了，我覺得我沒有利用CUDA的並行功能，因爲在樹的每一層都創建了N/2^i線程，在合併所有相鄰的船體時，複雜度爲O（N）。因此，網絡複雜性仍然是O（N logN）。
你能告訴我如何讓它變得更好嗎？或者爲凸包提供任何替代的整理器並行算法（如果我可以得到graham掃描的並行版本的算法，那將會很棒）？