An O(nlog ² 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(nlog ² h)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, if h = o(2√log ₂ n ), of the O(nlog n) time divide-and-conquer algorithm.