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.

I am investigating a convex hull algorithm that involves sorting. In fact, its running time is limited by sorting, so it is $O(n \log n)$, where $n$ is the number of points on the plane.

That algorithm first sorts the points by x-coordinates. It then includes the first and last points in the convex hull. From there on, I am confused. How could an algorithm like this get the other points of the hull?

share|improve this question
3  
Which algorithm are you looking at? There are several that involve sorting (q.v. Convex Hull Algorithms on Wikipedia). –  Luke Mathieson Nov 30 '12 at 7:56
1  
He is most likely talking about the incremental algorithm for the convex hull. What I do not understand is what exactly is your misunderstanding, David? –  Jernej Nov 30 '12 at 9:42

1 Answer 1

It is easier to catch the connection with sorting if you first sort the points by their polar angle. This is the basic idea for the Graham scan. Though, the idea with sorting points by the x-coordinates also works: you need then to apply just a slight modification of the same Graham's algorithm.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.