TY - JOUR
AB - An algorithm is presented that constructs the convex hull of a set of n points in three dimensions in worst-case time O(n log2h) and storage O(n), where h is the number of extreme points. This is an improvement of the O(nh) time gift-wrapping algorithm and, for certain values of h, of the O(n log n) time divide-and-conquer algorithm.
AU - Edelsbrunner, Herbert
AU - Shi, Weiping
ID - 4051
IS - 2
JF - SIAM Journal on Computing
SN - 0097-5397
TI - An O(n log^2 h) time algorithm for the three-dimensional convex hull problem
VL - 20
ER -