2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Which algorithm are you looking at? There are several that involve sorting (q.v. Convex Hull Algorithms on Wikipedia). $\endgroup$ – Luke Mathieson Nov 30 '12 at 7:56
  • 1
    $\begingroup$ 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? $\endgroup$ – Jernej Nov 30 '12 at 9:42
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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