An $O(n\log ^2 h)$ Time Algorithm for the Three-Dimensional Convex Hull Problem
Herbert Edelsbrunner, Weiping Shi · SIAM Journal on Computing · 1991
An algorithm is presented that constructs the convex hull of a set of n points in three dimensions in worst-case time $O(n\log ^2 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^{\sqrt {\log _2 n} } )$, of the $O(n\log n)$ time divide-and-conquer algorithm.