c - Cudaの凸多角形アルゴリズム?

Question

Cudaを使用してすべてのランダムポイントを含む凸多角形を見つけるアルゴリズムを探しています。私が適応できる非常に効率的なアルゴリズムを知っている人はいますか?

score 3 · Accepted Answer

あなた（または将来のSOユーザー）がまだCUDA用の3Dハルアルゴリズムを探しているなら、2011年11月からこの論文をチェックするかもしれません：

「CudaHull：GPU上の高速並列3D凸包」、Ayal Stein、Eran Geva、およびJihad El-Sana

著者は、Qhull（http://www.qhull.org）の27倍から40倍の高速化を、それぞれ1,000万ポイントと2,000万ポイントと主張しています。ただし、ポイントが少ない場合（<10,000）、CPU/GPUアルゴリズムは実際にはQhullよりも低速です。

私自身は実装していませんが、CUDAの3D凸包アルゴリズムを検索しているときに、SOの質問とCudaHullの論文の両方に出くわしました。

score 1 · Accepted Answer

CUDAを使用してGPUで凸包アルゴリズムを実行することについてHiPCで発表された論文があります。

グラハムスキャンは、一連の点の凸包を見つけるための単純なアルゴリズムです。ウィキペディアの記事には、その擬似コードバージョンがあります。

2 に答える 2