Answers are grounded in this paper and cite their sources.
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 ) . • A new set of points that causes Quickhull to take quadratic time. • A Quickhull lower bound that depends on the convex hull size. • A counterexample for the Quickhull precision conjecture of Barber et al.
No takes yet. Share an insight, caveat, or question.
Michael T. Goodrich (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: