The Graham scan algorithm computes the convex hull of a finite sets of points. It works only in the plane but is also fast (time $O(n \log n)$).

An old exam question asks, why does the algorithm not extend for three dimensional space? I just can't find an answer; it seems to me as if it should work.

  • Sorting the points according to a pivot should not be a problem.
  • Detecting a Left/Right turn (or measering the inner angle) neither.

Then what is the problem when we try to extend the algorithm to three dimensions?

  • 1
    $\begingroup$ Could you please elaborate? $\endgroup$ – mrk Jan 26 '13 at 0:15
  • $\begingroup$ i added the wiki link for Graham Scan. $\endgroup$ – A.B. Jan 26 '13 at 0:49
  • $\begingroup$ Detecting left/right also not ? How ? I dont think so. I guess you are talking about the projection of points on a 2-D hyperplane. Also, in 3D, you will not consider left and right only. $\endgroup$ – AJed Jan 26 '13 at 2:24
  • 2
    $\begingroup$ There is no natural linear ordering of the points on a surface homeomorphic to a sphere. It would not be clear which point to add next, nor clear whether to accept a point and push further. $\endgroup$ – Joseph O'Rourke Jan 26 '13 at 15:11
  • $\begingroup$ i dont understand why it should be a problem to sort them according to 2 choosen axis (e.g. according to (x/y)). And when detecting (just literally) left/right we can take into account the z-coordinate. Am i right? $\endgroup$ – A.B. Jan 26 '13 at 16:55

Your Answer

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

Browse other questions tagged or ask your own question.