A lower bound for the Quickhull convex hull algorithm that disproves the Quickhull precision conjecture
Michael T. Goodrich · Information Processing Letters · 2025
The Quickhull algorithm is a simple algorithm for constructing the convex hull of a set of n points. Quickhull is usually described for points in the plane, in which case it is defined as a divide-and-conquer algorithm, where one has a pair of points ( p , r ) such that p and r are on the convex hull, and one then finds the point, q , farthest from the line p r ‾ , which must also be on the convex hull, and then uses the triangle ( p , q , r ) to divide the remaining points and recursively solve the resulting subproblems. It is well-known that Quickhull has a worst-case running time of Θ ( n 2 ) , but it runs much faster than this for some input distributions. In a highly cited paper, Barber, Dobkin, and Huhdanpaa conjecture that the Quickhull algorithm runs in worst-case O ( n log h ) time, where h is the size of the convex hull, when the input points have precision O ( log n ) . In this paper, we give an explicit lower-bound construction that shows that, in general, the worst-case running time of the Quickhull algorithm is Θ ( n h ) . Our lower bound proof also provides a counter-example to the Quickhull precision conjecture of Barber et al., in that we give an explicit construction of a set, S , of n points with precision O ( log n ) such that h is O ( log n ) but the worst-case running time of Quickhull on S is Θ ( n h ) , not O ( n log h ) .