Quickhull vs T.M. Chan vs Avis and Fukuda

Question

From Discrete lizard's answer and Handbook of Computational Geometry (Third edition, 2018) Section 26, Chazelle's solution of high dimensional convex hull achieved worst case optimal. T.M. Chan's algorithm made the practical implementation, and Avis and K. Fukuda's solution was more efficient.

However, I recently came across the Quickhull algorithm based on Qhull librtary, and from Mauricio Fernández's answer, it seemed that the Quickhull was faster than T.M. Chan's algorithm. This confused me a bit because T.M. Chan's algorithm was designed specifically for the high dimensional convex hull computation, while the Quickhull arise from the lower dimensional algorithms.

Which algorithm was faster in theory and which algorithm is faster in practical, Quickhull,T.M. Chan's algorithm, or Avis and Fukuda's algorithm?

Answer 1

"Faster" has no meaning when you compare theoretical algorithms. In general the complexities are only known asymptotically, and for practical problem sizes these expressions can be completely irrelevant. Furthermore, in practice you deal more with expected complexities than with worst cases, and the former can strongly depend on the data distribution.

In the case of the convex hull, an important aspect is how soon the internal sites are discarded, leaving only the hull vertices. QuickHull is good at that and might perform favorably when $h$ is small (the expected complexity can drop to $O(n)$), though its worst-case complexity is terrible ($O(n^2)$).