A divide-and-conquer algorithm for computing 4-dimensional convex hulls

This paper contains a description an algorithm for computing four dimensional convex hulls of point sets using the divide-and-conquer paradigm. The algorithm features minimal asymptotic time and memory complexity with respect to the size of its input point set. It is based upon a fully-dual four-dimensional boundary representation (BREP) data structure called Hexblock, also developed by the author, which was inspired by Guibas' and Stolfi's quadedge data structure.The algorithm was developed in order to quickly compute three-dimensional Delaunay triangulations of large numbers of points. It has been implemented. Also implemented for comparison purposes was a more conventional algorithm for computing such triangulations due to Sever. Preliminary tests suggest that the implementations in fact perform commensurate with theoretical expectations.