Some parallel geometric algorithms

These notes review some techniques of computational geometry which parallelise well. Specifically, the construction of convex hulls in two dimensions and three dimensions and the Voronoi diagram for sets of points in two dimensions, and some methods for planar point location, are described. The theme is the application of refined techniques to a few problems: the more abstract questions of parallel complexity do not arise; and for lack of space some important methods, such as randomisation, are not covered.