3
$\begingroup$

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 ?

$\endgroup$
2
  • $\begingroup$ I would say the main differences of these algorithms come from understanding the question from different perspectives. They all work in $O(n\log(n))$, and hence the reason you learn them all in a computational geometry course is that they give different perspectives to problems, which can be useful for constructing other algorithms for other problems later on. $\endgroup$ – nir shahar Jun 19 at 13:45
  • $\begingroup$ @nirshahar not correct: gift-wrapping can be require order of $n^2$ time in the worst-case (when a constant fraction of points lie on the hull). $\endgroup$ – Vincenzo Jun 19 at 20:03
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.