Consider a polygonal curve $P$ consisting of a sequence of vertices $(p_1,…, p_n)$. The curve is not closed, meaning that $p_1 ≠ p_n$. The curve has the property that each vertex makes left-turn, that is, orient $(p_{i-1},p_i,p_{i+1}) > 0$, for $2 ≤ i ≤ n−1$ (see Fig.).
The problem is to design an efficient algorithm (ideally running in $O(n)$ time) that determines whether $P$ is simple, meaning that no two nonadjacent edges of $P$ intersect one another (see Fig.(a) and (b)).
Now actually a problem: for $2 ≤ i ≤ n−1$, define $\theta_i$ be the counterclockwise angle from the directed vector $v_{i-1}→v_i$ to $v_i→v_{i+1}$. The turning number of $P$, denoted $turn(P)$, is defined to be $$turn(P) := \sum_{i=2}^{n-2}\frac{\theta_i}{2\pi}.$$ I need to derive an algorithm for testing the simplicity of $P$, assuming that $turn(P) ≤ 1$. That is, the curve cannot make a spiral.
I know from Preparata, Shamos p.172-173 of a problem called DEPTH OF A SET. So this problem finds a "depth" of every point $p$ in set -- number of convex hulls, made for our points, which have to be stripped from our set of points before $p$ is removed. Better to show an image:
So I think I could use here that? Because it seems simple curves have depth of points of the curve equal to one, when self-intersecting seems to have number equal more than one.
Any ideas how to solve this? Maybe I need an another approach?
Not an answer, just some insight. If you consider growing the polygon until a certain vertex, the allowed area for the next vertex is the visibility graph of the current vertex (in white in the two examples below and using the fact that the turn is only left).
It is possible that the update of the visibility graph can be made incrementally, with a constant amortized time per vertex (?). Anyway, it is dubious that testing the next vertex against this graph can also be done in constant amortized time.