Abstract
Computing the convex hull of a set of points in the plane is one of the most studied problems in computational geometry. The Quickhull algorithm is a popular convex hull algorithm. While the main structure of Quickhull is axed, many different variants have been suggested. In all instances, traditional analysis states the best-case running time of Quickhull as O(n log n) and the worst-case as O(n²), where n is the number of input points. In this thesis, we identify a particular variant of Quickhull as being more efficient than others. We provide an analysis that shows this version of Quickhull, which we call VQHull, runs in expected O(n) time for points uniformly distributed in the plane, and O(n log n) expected time for uniformly distributed extreme input. This is the first time this remarkable property of this version of Quickhull has been noted. We also provide empirical evidence showing that VQHull will outperform other variants of Quickhull and also other popular convex hull algorithms. Parallel algorithms for computing the convex hull have also relieved much attention. However, Quickhull has so far not been identified as an attractive algorithm for parallel implementation, mainly due to problems thought to exist in obtaining good load balance. In this thesis we show that such concerns are unwarranted by providing a simple, efficient parallelization of VQHull. In particular, for uniform in- put, our parallel counterpart runs in O([] + log h log p) expected time and performs O(n + p log h log p) work, where p is the number of processors and h is the number of facets of the final convex hull. When the input is extreme, the parallel algorithm runs in O([] log n + log n log p) expected time and O(n log n + p log n log p) work. In summary, the contributions are two-fold. First, we establish one particular efficient variant of Quickhull. Second, we show that the Quickhull algorithms in general, and VQHull in particular, are good candidates for parallelization.
Sambasivam, Mashilamani (1999). VeriQuickhull: fast sequential and parallel algorithms for computing the planar convex hull. Master's thesis, Texas A&M University. Available electronically from
https : / /hdl .handle .net /1969 .1 /ETD -TAMU -1999 -THESIS -S2552.