Parallel computational geometry

We present efficient parallel algorithms for several basic problems in computational geometry: convex hulls, Voronoi diagrams, detecting line-segment intersections, triangulating simple polygons, minimising a circumscribing triangle, and recursive data-structures for 3-dimensional queries.