A simple mathematical promise allows computers to calculate a convex hull faster than the fundamental O(n log n) speed limit that has governed the field for decades.
Geometry textbooks teach that sorting points to find their outer boundary has a fixed computational floor. This algorithm breaks that floor by assuming the input sequence already contains the hull as a hidden subsequence. This promise bypasses the traditional bottleneck of comparing every point against every other point. While the speedup seems theoretical, it changes how we approach massive spatial datasets in geographic information systems. Engineers used to accept the O(n log n) limit as an unbreakable law of nature. This proof shows that knowing just a little bit about your data structure can enable performance previously thought to be mathematically impossible.
Computing Planar Convex Hulls with a Promise
arXiv · 2605.03904
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 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 we