Computing Planar Convex Hulls with a Promise
For computational geometry researchers, it provides a new conditional lower bound and algorithms that exploit a weak ordering promise, resolving an open problem.
The paper shows that under the promise that the input sequence contains the convex hull as a subsequence, the planar convex hull can be computed in O(n sqrt(log n)) deterministic time or O(n log^ε n) randomized time, breaking the Ω(n log n) lower bound. This promise is tight: if even one hull point is out of order, the lower bound returns.
Computing the convex hull of a planar $n$-point set $P$ is one of the most fundamental problems in computational geometry. It has an $Ω(n \log n)$ lower bound in the algebraic computation tree model, and many convex hull algorithms match this bound. Classical results show that, under special input assumptions, sub-$O(n \log n)$ algorithms are possible. For instance, when the points are given in lexicographic or angular order, the convex hull can be computed in linear time. Even under the weaker assumption that the sequence of points corresponds to the ordered vertices of a simple polygonal chain, linear-time algorithms exist. This naturally raises the question: can the convex hull of a point set be computed in sub-$O(n \log n)$ time under weaker input assumptions? We answer this positively. Under the promise that the input sequence contains the convex hull as a subsequence, we give a deterministic $O(n \sqrt{\log n})$-time algorithm to compute the convex hull of $P$. With randomisation, we achieve expected running time $O(n \log^{\varepsilon} n)$ for any constant $\varepsilon > 0$. We find this surprising, as points not on the convex hull may behave adversarially toward our convex hull construction algorithm. Yet the promise that \emph{only} the hull points are sorted suffices for $o(n \log n)$-time algorithms. Finally, we show that this promise is tight: if it is even slightly broken, i.e., allowing just one hull point to appear out of order, we prove an adversarial $Ω(n \log n)$-time lower bound. Consequently, the promise cannot be verified with fewer than $Ω(n \log n)$ comparisons. This also negatively resolves an open problem of Löffler and Raichel, who conjectured sub-$O(n \log n)$-time algorithms for computing the convex hull of a supersequence containing the hull as a subsequence.