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?

  • 1
    $\begingroup$ how is $P$ given to you? if it can be given in arbitrary order, then the assumption in bold can clearly fail. $\endgroup$ Dec 11 '12 at 3:56
  • 4
    $\begingroup$ This is a first-week homework exercise in any computational geometry course. Hint: Winding number. $\endgroup$
    – JeffE
    Dec 11 '12 at 4:33
  • $\begingroup$ Do we know this problem is insoluble in linear time if the points are given in arbitrary order? $\endgroup$
    – usul
    Dec 11 '12 at 18:57
  • $\begingroup$ @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. $\endgroup$
    – Jmoney38
    Dec 11 '12 at 23:13
  • $\begingroup$ @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. $\endgroup$
    – 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$.

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.


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.