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?
