# How does sorting come into play with convex hull?

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?

-
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
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

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.

-