Monma et al. solve this in O(n log h)
time and O(n)
space, where n
is the number of points and h
is the size of the convex hull.
The algorithm (p.10 of the paper) is fairly simple so it should be accessible even without understanding the full proof.