Cudaの凸多角形アルゴリズムですか？

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

2011-01-27 Dark

これは標準的な凸包の問題ではありません：http://en.wikipedia.org/wiki/Convex_hull？ –

これは3dの凸包ですが、実際は標準です。しかし、問題はCUDA GPUマルチスレッドにマップする効率的なアルゴリズムを見つけることです。 – Dark

Convex Hull AlgorithmをCUDAを搭載したGPUに実行することに関するpaper presented at HiPCがあります。

Graham Scanは、一連の点の凸包を見つける簡単なアルゴリズムです。 Wikipediaの記事には、その疑似コードバージョンが存在します。

2011-01-27 13:43:28 vz0

ええ、私はその論文を知っていますが、それは2次元版です。さらに、Graham Scanは3Dに拡張することは不可能だと思われます。しかし、とにかく答えてくれてありがとう – Dark

あなた（または将来のユーザーSO）の場合は、まだCUDAのための3Dハルアルゴリズムを探している、あなたは2011年11月からこの論文をチェックアウトすることがあります

「CudaHull：GPU上での高速パラレル3D凸包」 Ayalスタイン、エランGEVA、及びジハードエルサナによって

著者らは、それぞれ、10の2000万点についてQhull（http://www.qhull.org）上27X 40倍に高速化を主張します。しかし、より少ないポイント（< 10,000）では、CPU/GPUアルゴリズムは実際にQhullよりも遅くなります。

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

2012-01-30 22:19:08 Rethunk

答えて