Is there a special algorithm for computing the convex hull ordering when the candidate points are on the hull?

I'm dealing with a set of points which are already placed on the 2D hull boundary: a convex polygon. I know this for sure. However, the point set is not ordered, and I need the polygon points to be ordered counter-clockwise.

I'm aware of all the 2D algorithms for convex hull generation from the books/literature, but I'm interested if there is a faster, specialized, algorithm for this special case?

2 Answers

Take the mean of all your points as origin and transform to polar coordinates. This gives the desired ordering in $O(n\log n)$ operations.

• Yes all the points are already on the hull boundary. I've corrected the question. – tmaric Jul 11 '12 at 14:45
• If the points are on the hull, isn't the right way to go to skip all the processing pertained to interior point elimination from standard hull algorithms, and sort the points with respect to say angle defined by the centrepoint of the hull (e.g. incremental sort)? – tmaric Jul 11 '12 at 14:49
• @tomislav-maric: And I corrected my answer; one can indeed take advantage of the given assumption. – Arnold Neumaier Jul 11 '12 at 14:53

Since the points are in 2D, you can use Graham's Scan to order the points instead of a sorting algorithm. This will also give you a $\Theta(nlog(n))$ complexity without the need for any transformations.

• Grahams scan involves searching for interior points, and sorting with respect to angle; the transformation to polar coordinates is basically the angle based search in 2D... – tmaric Jul 11 '12 at 18:12