Parallel computational geometry algorithms

This page contains a collection of parallel computational geometry algorithm. It includes a brief description of each algorithm along with the NESL code. These algorithms have been developed by the Scandal project.

If you have arrived here via a search engine, we suggest going to the toplevel algorithms page.


This is a parallel version of Quickhull. Quickhull is a divide and conquer algorithm for finding a convex hull and has an expected complexity of O(n log n) work and O(log n) depth.

Kirkpatric and Seidel Convex Hull

This is the algorithm from the Kirkpatrick and Seidel paper "The Ultimate Planar Convex Hull Algorithm?". For f points in the result it does O(n log f) work and has O(log^2 n log f) depth.