QuickhullDisk: A faster convex hull algorithm for disks

摘要

Convex hull is one of the most fundamental constructs in geometry and its construction has been extensively studied. There are many prior works on the convex hull of points. However, its counterpart for weighted points has not been sufficiently addressed despite important applications. Here, we present a simple and fast algorithm, QuickhullDisk, for the convex hull of a set of disks in R2 by generalizing the quickhull algorithm for points. QuickhullDisk takes O(nlog n) time on average and O(mn) time in the worst case where m represents the number of extreme disks which contribute to the boundary of the convex hull of n disks. These time complexities are identical to those of the quickhull algorithm for points in R2. Experimental result shows that the proposed QuickhullDisk algorithm runs significantly faster than the O(nlog n) time incremental algorithm, proposed by Devillers and Golin in 1995, particularly for big data. QuickhullDisk is approximately 2.6 times faster than the incremental algorithm for random disks and is 1.2 times faster even for the disk sets where all disks are extreme. This speed-up is because the basic geometric operation of the QuickhullDisk algorithm is a predicate for the location of a point w.r.t. a line and is much faster than that of the incremental algorithm. The source code of QuickhullDisk is freely available from Mendeley Data and a GUI-version from Voronoi Diagram Research Center, Hanyang University (http://voronoi.hanyang.ac.kr/).