Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

migrated from cstheory.stackexchange.com Dec 11 '12 at 23:23

This question came from our site for theoretical computer scientists and researchers in related fields.

1  
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
4  
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
show 2 more comments

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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