Computing Planar Convex Hulls with a Promise

Sepideh Aghamolaei, Kevin Buchin, Timothy M. Chan +5

Computing the convex hull of a planar $n$-point set $P$ is one of the most fundamental problems in computational geometry. It has an $\hat{I}\text{c◯}(n\log n)$ lower bound in the algebraic com…