An O(n log^2 h) time algorithm for the three-dimensional convex hull problem
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.
20
2
259 - 269
259 - 269
SIAM