Validating a sequence of points as a convex hull

Question

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?

Answer 1

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

See this paper for analogues in higher dimension.

Interestingly, in the smooth version (CCW turn is here positive sectional curvature), for a 1d curve you still have to check the winding number, but by an old theorem of Hadamard, if higher dimensional (immersed) manifolds have positive sectional curvature everywhere, then they enclose a convex body.