# Why does Graham Scan not extend to three dimensions?

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?

• Could you please elaborate? – saadtaame Jan 26 '13 at 0:15
• i added the wiki link for Graham Scan. – A.B. 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? – A.B. Jan 26 '13 at 16:55