Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|improve this question
1  
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
2  
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

 
discard

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

Browse other questions tagged or ask your own question.