在GPU上的并行凸包算法

Question

我正在使用CUDA实现凸包的分治方法。这是我的方法： 自底向上：

• 创建一个列表来存储凸壳；
• curSize = 输入的大小（所有点）；
• 对于i：1到log N
• 开始
• curSize = curSize / 2；
• 在列表中取出每2个相邻的凸壳，并将它们合并成更大的凸壳（使用标准的上下公切线方法进行分治凸壳），在当前尺寸的线程中执行
• //最初，它将列表中的每两个相邻点合并成一个凸壳，然后在下一次迭代中，将大小为2的凸壳合并成更大的凸壳等等......最终，列表将有一个点列表，表示凸壳
• 结束

但是这变得太复杂了，我感觉没有充分利用CUDA的并行能力，因为在树的每个级别上，我都会创建N/2^i个线程，其复杂度为O(N)，用于在该级别合并所有相邻的凸壳。因此，网络复杂度仍为O(N logN)。

你能告诉我如何改进它或提供任何替代的更好的并行凸包算法吗（如果我能获得Graham扫描的并行版本的算法将会很棒）？

- alpha_cod

Answer 1

你的算法复杂度仍然是O(N)（与单线程版本相比没有改变），因为你做了三件事：

1. 管理线程：O(N)
2. 从列表中删除一些顶点：摊销O(N)，因为只有N个点。
3. 查看已删除但在当前步骤中未被删除的相邻点：O(N)，因为每次合并不会超过2个这样的点。

但如果你的点没有排序，最好并行化排序。

- Sergey Bankevich