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 $\Omega (n\log n)$ lower bound in the algebraic comp…