Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Could you please elaborate? – saadtaame Jan 26 '13 at 0:15
i added the wiki link for Graham Scan. – Hasan Tahsin Jan 26 '13 at 0:49
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. – AJed Jan 26 '13 at 2:24
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. – Joseph O'Rourke Jan 26 '13 at 15:11
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? – Hasan Tahsin Jan 26 '13 at 16:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.