# Validating a sequence of points as a convex hull

I'm familiar with the classical convex hull calculation algorithms. The lower bound for computing the CH of a set of points $P$ is $n\log(n)$.

However, what if I'm given a sequence of points and told they form a CH? One check is to "walk the points" in order and check for "left turns" (CCW). However, this doesn't handle the case of self-intersections (you could imagine a counter-example that "winds around starting from the center" making only CCW turns.

I've been told this "validation" can be done in $O(n)$ time, but to check for self-intersection naively, I see $O(n^2)$ time.

My next thought is to run Graham's Scan. Since the points are presumably on a CH, it takes $O(n)$ to find the lower left point, say $p_0$, and from there, I THINK you can guarantee that all points $p_1, p_2,\dots,p_n$ are already sorted by angle between $p_0$ and $x$-axis. As you move the three-point-window forward along the hull, the points ahead are still properly sorted. The reasoning for $O(n)$ then follows per normal reasoning for Graham's scan, minus the need for $O(n\log n)$ sorting.

1) Is my assumption, in bold, correct?
2) Is there an easier method that wouldn't involve running Graham's scan?

• how is $P$ given to you? if it can be given in arbitrary order, then the assumption in bold can clearly fail. – Sasho Nikolov Dec 11 '12 at 3:56
• This is a first-week homework exercise in any computational geometry course. Hint: Winding number. – JeffE Dec 11 '12 at 4:33
• Do we know this problem is insoluble in linear time if the points are given in arbitrary order? – usul Dec 11 '12 at 18:57
• @SashoNikolov - Maybe it wasn't clear enough in the O.P. - A sequence of points that is supposed to be a traversal of the CH - so essentially, we're trying to validate if the given sequence, not set, is a convex hull. – Jmoney38 Dec 11 '12 at 23:13
• @JeffE - This is not a HW question, nor is it for a computational geometry class. But thanks for the backhanded comment. The winding number is interesting, but it seems like finding a position within the sequence of points to form the ray, and choosing a direction, would not guarantee that multiple edges would be crossed in a self-intersecting sequence. I'm not sure if WN is the correct solution for this problem. – Jmoney38 Dec 12 '12 at 0:00

The answer is easier than you think. As you remarked you should check if you take always CCW or CW turns. But of course, this might result in a curve that is self-intersecting. But you can detect this easily, just sum up then angles of the "turns". Since your curve is closed this angle sum is a multiple of $2\pi$. If it winds up exactly once it does not self-intersect. In this case the angle sum is $2\pi$. Thus you are left with checking, if the angles sum up to $2\pi$.