I was wondering what are the main differences in terms of efficiency of convex hull algorithms? Brute force algorithm is inefficient due to iterating over every three vertices in our set and its time complexity is $O(n^3)$ and probably is never good to use. But what about Gift wrapping, Graham's scan and Chan's algorithm? My understanding is that Graham scan and Chan's are efficient, Graham scan on smallers sets and Chan's algorithm on bigger sets but what are main pros and cons of those three algorithms? When to use which ?
If $n$ is the number of 2D points, let $h \le n$ be the number of points on the convex hull. Then:
- Gift wrapping takes time $\Theta(n h)$, which can be $\Theta(n^2)$ in the worst case. It is relatively simple to implement. Gift-wrapping generalizes to 3 dimensions and beyond.
- Graham scan takes time $O(n \log n)$. It is very easy to implement especially if you use the so-called monotone chain (also known as Andrew scan) variant. It does not generalize easily to 3 dimensions and beyond.
- Chan's algorithm takes time $O(n \log h)$, which is asymptotically optimal. It is somewhat more sophisticated to implement than the Graham scan. It generalizes to 3 dimensions.
Therefore, my suggestion would be:
If your points are 2D, go for the Andrew scan. The difference between $\log h$ and $\log n$ may not be worth the extra complications of Chan's algorithm unless your dataset is truly huge.
If your points are 3D, Chan's algorithm makes sense and is faster than gift-wrapping in the worst-case.
If your points are in higher dimension than 3D, use gift-wrapping, since the other algorithms either don't work or require very complex adaptations anyway.