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 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 . 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/).
Keywords for this software
References in zbMATH (referenced in 5 articles , 1 standard article )
Showing results 1 to 5 of 5.
- An, Phan Thanh; Hoang, Nam Dung; Linh, Nguyen Kieu: The lifting projection of convex polyhedra for finding Delaunay triangulations (2022)
- An, Phan Thanh; Huyen, Phong Thi Thu; Le, Nguyen Thi: A modified Graham’s convex hull algorithm for finding the connected orthogonal convex hull of a finite planar point set (2021)
- Kallrath, Josef; Ryu, Joonghyun; Song, Chanyoung; Lee, Mokwon; Kim, Deok-Soo: Near optimal minimal convex hulls of disks (2021)
- An, Phan Thanh; Hoang, Nam Dũng; Linh, Nguyen Kieu: An efficient improvement of gift wrapping algorithm for computing the convex hull of a finite set of points in (\mathbbR^n) (2020)
- Nguyen Kieu Linh; Song, Chanyoung; Ryu, Joonghyun; Phan Thanh An; Hoang, Nam-Dũng; Kim, Deok-Soo: QuickhullDisk: a faster convex hull algorithm for disks (2019)