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.
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.