<p>At Pat Morin's suggestion, here is my idea for computing the turning number.  Sorry if this is a bit sloppy; I'm still fighting the notation demons.  Moreover, Pat's comment to Chris's answer reveals that I've ignored some important degenerate cases.  But I'll post this here anyway in case others find it useful.</p>

<p>For any index $i$, let $\theta(p_i) = \theta(p_{i-1}, p_i, p_{i+1})$ denote the <em>signed external angle</em> at vertex $p_i$; this is the counterclockwise angle between the rays $\overrightarrow{p_{i-1}p_i}$ and $\overrightarrow{p_ip_{i+1}}$, normalized to the range $-\pi \le \theta_i \le \pi$.  (All index arithmetic is implicitly mod $n$.)  The <a href="http://en.wikipedia.org/wiki/Winding_number#Turning_number" rel="nofollow"><em>turning number</em></a> of $P$ is defined as
$$
Turn(P) = \frac{1}{2\pi} \sum_{i=0}^{n-1} \theta(p_i).
$$
Let me call a vertex $p_i$ a <em>spur</em> if the <em>internal</em> angle at $p_i$ is equal to $0$.  The external angle $\theta_i$ at a spur is not well-defined; it could be either $\pi$ or $-\pi$.  More generally, the turning number of $P$ is well-defined if and only if $P$ has no spurs (and no repeated vertices $p_i=p_{i+1}$).  It's not hard to prove that $Turn(P)$ is an integer if it is well-defined; in particular, $Turn(P) = \pm 1$ if $P$ is a simple polygon.</p>

<p>Now suppose $P$ contains a walk of the form $p\mathord\to r\mathord\leadsto s\mathord\leadsto r\mathord\to q$, where $p\ne q$ and the path $r\mathord\leadsto s$ is the reversal of the path $s\mathord\leadsto r$.  Then $s$ is a spur; call $r$ the <em>root</em> of $s$.  In this case, let me <em>define</em> the external angle at $s$ as follows:
$$
  \tilde\theta(s) = \pi \cdot \mathop{sgn}\theta(p, r, q) =
\begin{cases}
   \pi &amp; \text{if } \theta(p, r, q) &gt; 0\\
   -\pi &amp; \text{if } \theta(p, r, q) &lt; 0
\end{cases}
$$
<strong>(But what if $\theta(p,r,q)=0$?  As Pat observes, this can actually happen.  Probably there's some sort of recursive way to define $\tilde\theta(s)$ even in this case, but I don't know what it is.)</strong></p>

<p>If $P$ is weakly simple, then there is a simple $n$-gon $\tilde{P}$ arbitrarily close to $P$; tet $\tilde{s}$ be the vertex of $\tilde{P}$ closest to $P$.  As $\tilde{P}$ approaches $P$, the internal angle at $\tilde{s}$ approaches zero.  It's not hard to prove (by induction on the length of $r\mathord\leadsto s$) that the external angle $\theta(\tilde{s})$ approaches $\tilde\theta(s)$.</p>

<p>If $P$ consists entirely of a walk followed by its reversal, $r\mathord\leadsto s\mathord\leadsto r$, then the external angles at the spurs $r$ and $s$ are still not well-defined.  But in this case, I believe $P$ is weakly simple if and only if the walk $r\mathord\leadsto s$ is non-self-crossing.  <strong>(There are more complex cases where I cannot define a reasonable modified turning number, in particular, if the polygon wanders back and forth through a single walk.  But in all such cases, it appears that the polygon is weakly simple if and only if it is non-self-crossing.)</strong></p>

<p>Otherwise, if we define $\tilde\theta(p_i) = \theta(p_i)$ for any non-spur vertex $p_i$, we now have a well-defined turning number $\widetilde{Turn}(P) = \sum_i\tilde\theta(p_i)/2\pi = Turn(\tilde{P})$, which must be $\pm 1$ if $P$ is weakly simple.</p>

<p>I'm no longer confident that $\widetilde{Turn}(P)$ can be computed in linear time.  The main difficulty is that the walk $r\mathord\leadsto s$ can itself contain spurs.  The naive algorithm that finds the root of each spur by brute force actually takes $\Theta(n^2)$ time in the worst case; consider an $n$-gon that has a subwalk of length $\Omega(n)$ that simply alternates between two points.</p>

CC BY-SA 3.0
2012-06-01T07:02:11.247Z
2012-06-01T07:02:11.247Z
Jeffε
<p>It seems like the first question has a $O(n^3)$ algorithm (though this is also likely not optimal).  Assuming that there is a crossing, the key to finding it seems to be that the edges that must be found are those immediately on either side of the common subpath.  Therefore, we look at all pairs of consecutive pairs of edges.  There are a quadratic number of these.  If we find a pair of pairs of edges with vertices $abc$ and $def$ such that edges $bc$ and $ef$ are the same, then we follow the common subpath to the end and inspect the edges that leave it.  If they form a crossing along with $ab$ and $de$, then we are done, otherwise we go on to the next pair.  Following the common subpath is at most a linear-time operation, so the whole algorithm is $O(n^3)$.</p>

<p>This analysis probably isn't tight since the number of times a linear-length common subpath will be followed isn't linear in the number of pairs of pairs.  There should be only a constant number of those.  Similarly, if the length of the longest common subpath is constant, then we are okay in terms of the amount of time following common subpaths.  I would expect that the worst case arises when there is a single subpath of length $O(\sqrt{n})$ that is common to $O(\sqrt{n})$ subpaths.  Then there are $O(n)$ interactions and in each interaction $O(\sqrt{n})$ edges are being followed.  So even still, the number of edges that are followed is $o(n^2)$, and the bound is provided by the number of pairs.  Thus I would guess that the true bound for this algorithm is $O(n^2)$. </p>

CC BY-SA 3.0
2012-05-30T15:41:04.583Z
"Following the common subpath is at most a linear-time operation..."  Is this true?  Remember that the subpaths are not identical.  One may be folding back and forth along the image of the other.  In fact, it's not even clear (to me) when you know you're done.
Pat Morin
CC BY-SA 3.0
2012-05-31T01:35:07.107Z
Good point.  Would it be possible, as a preprocessing step, to put the polygon in some kind of standard form?  We would elide paths that immediately fold back on themselves, as well as vertices that are collinear with their immediate neighbors.  Then the sentence that you quoted would be better defined -- the common subpath consists of edges that have the same vertices, and you know that you are done because you hit different vertices.  Proving that the answer remains the same in the polygon in standard form should not be too hard.
Chris Gray
CC BY-SA 3.0
2012-05-31T08:31:02.290Z
@ChrisGray: Maybe, but not quite as easily as you've suggested.  If the image of $P$ is a tree, then recursively eliding _all_ switchbacks eventually reduces $P$ to a single point.
Jeffε
CC BY-SA 3.0
2012-05-31T22:55:19.827Z
Yes, you're right, that idea won't work.  The rightmost figure you gave above would be reduced to a single point.
Chris Gray
CC BY-SA 3.0
2012-06-01T06:56:59.320Z
I'm plan to let the bounty expire; half the points will be automatically awarded to this answer.
Jeffε
CC BY-SA 3.0
2012-05-26T06:46:34.063Z
2012-05-26T06:46:34.063Z
Chris Gray
<p>I'm interested in the complexity of deciding whether a given non-simple polygon is <em>almost</em> simple, in either of two different formal senses: <em>weakly simple</em> or <em>non-self-crossing</em>.  Since these terms are not widely known, let me start with some definitions.</p>

<ul>
<li><p>A <strong>polygon</strong> $P$ is the closed cycle of line segments connecting some finite sequence $p_0, p_1, p_2, \dots, p_{n-1}$ of points in the plane.  The points $p_i$ are called the <em>vertices</em> of the polygon, and the segments $p_i p_{i+1\bmod n}$ are called its <em>edges</em>.  We can specify any polygon by just listing its vertices in order.</p></li>
<li><p>A polygon is <strong>simple</strong> if all $n$ vertices are distinct and edges intersect only at their endpoints.  Equivalently, a polygon is simple if it is homeomorphic to a circle and every edge has positive length.  In general, however, the vertices and edges of a polygon may intersect arbitrarily, or even coincide.<sup>1</sup></p></li>
<li><p>Consider two polygonal paths $A$ and $B$ whose intersection is a common subpath of both (possibly a single point).  We say that $A$ and $B$ <strong>cross</strong> if their endpoints $A(0), B(0), A(1), B(1)$ alternate on the boundary of a neighborhood of the common subpath $A\cap B$.  A polygon is <strong>self-crossing</strong> if it has two crossing subpaths and  <strong>non-self-crossing</strong> otherwise.<sup>2</sup></p></li>
<li><p>A polygon is <strong>weakly simple</strong> if it is the limit of a sequence of simple polygons, or equivalently, if there is an arbitrarily small perturbation of the vertices that makes the polygon simple.  Every weakly simple polygon is non-self-crossing; however, some non-self-crossing polygons are <em>not</em> weakly simple.</p></li>
</ul>

<p>For example, consider the six points $a,b,p,q,x,y$ shown below.</p>

<p><img src="https://i.sstatic.net/Wjs8f.png" alt="enter image description here"></p>

<ul>
<li><p>The polygon $abpqyz$ is simple; see the left figure.</p></li>
<li><p>The polygon $papbpqyqzq$ is weakly simple; the middle figure shows a nearby simple polygon.  However, this polygon is not simple, because it visits $p$ three times.</p></li>
<li><p>The polygon $papbpqzqyq$ is self-crossing, because the subpaths $bpqz$ and $yqpa$ cross.  See the right figure for some intuition.</p></li>
<li><p>Finally, the polygon $papbpqyqzqpapbpqyqzq$ (which winds twice around the middle polygon) is non-self-crossing, but it is <em>not</em> weakly simple.  Intuitively, the <a href="http://en.wikipedia.org/wiki/Winding_number#Turning_number" rel="nofollow noreferrer">turning number</a> of this polygon is $\pm 2$, while the turning number of any simple polygon must be $\pm 1$.  (A formal proof requires some case analysis, in part because the turning number is not actually well-defined for polygons with $0^\circ$ angles!)</p></li>
</ul>

<blockquote>
  <p><strong>Update (Sep 13):</strong> In the figure below, the polygon $abcabcxyzxpqrxzyx$ is non-self-crossing <strong>and has turning number 1</strong>, but it is not weakly simple.  The polygon arguably has several crossing <em>non-simple subwalks</em>, but it has no crossing <em>simple subpaths</em>.  (I say "arguably" because it's unclear how to define when two non-simple walks cross!)</p>
  
  <p><img src="https://i.sstatic.net/9R4hV.png" alt="enter image description here"></p>
</blockquote>

<p>So finally, here are my actual questions:</p>

<ul>
<li><p><strong>How quickly can we determine whether a given polygon is non-self-crossing?</strong></p></li>
<li><p><strong>How quickly can we determine whether a given polygon is weakly simple?</strong></p></li>
</ul>

<p>The first problem can be solved in $O(n^5)$ time as follows.  Since there are $n$ vertices, there are $O(n^2)$ vertex-to-vertex subpaths; we can test whether any particular subpath is simple in $O(n^2)$ time (by brute force).  For each pair of simple vertex-to-vertex subpaths, we can test whether they cross in $O(n)$ time.  But this <em>can't</em> be the best possible algorithm.</p>

<p>I don't know whether the second problem can be solved in polynomial time.  I think I can quickly compute a well-defined turning number for any non-simple polygon (unless the union of polygon edges is just a path, in which case the polygon must be weakly simple); see my answer below.  <strong>However, the new example polygon above implies that non-self-crossing and turning number 1 does <em>not</em> imply weakly simple.</strong></p>

<p>We can determine whether a given polygon is <em>simple</em> in $O(n^2)$ time by checking every pair of edges for intersection, or in $O(n\log n)$ time using a standard sweepline algorithm, or even in $O(n)$ time using Chazelle's triangulation algorithm.  (If the input polygon is not simple, any triangulation algorithm will either throw an exception, infinite-loop, or produce output that is not a valid triangulation.)  But none of these algorithms solve the problems I'm asking about.  </p>

<hr>

<p><sup>1</sup> Branko Grünbaum.  <a href="http://dx.doi.org/10.1007/s13366-011-0047-5" rel="nofollow noreferrer">Polygons: Meister was right and Poinsot was wrong but prevailed</a>. <em>Beiträge zur Algebra und Geometrie</em> 53(1):57–71, 2012. </p>

<p><sup>2</sup> See, for example:  Erik D. Demaine and Joseph O'Rourke.  <a href="http://gfalop.org/" rel="nofollow noreferrer"><em>Geometric Folding Algorithms: Linkages, Origami, Polyhedra</em></a>. Cambridge University Press, 2007.</p>

CC BY-SA 3.0
2012-05-24T18:22:46.050Z
I don't understand why one would down-vote this question?!
Kaveh
CC BY-SA 3.0
2012-05-24T18:50:22.440Z
I may be totally misunderstanding the question, and so maybe this is way off, but it would seem to me that the way you count vertices means that the second question necessarily takes exponential time.

Let me explain: In your last example you use the same vertices multiple times. It seems easy to construct graphs where there is an exponential number of unique cycles.
Joe Fitzsimons
CC BY-SA 3.0
2012-05-24T18:52:44.453Z
If your input is the polygon given as in your examples, then it is possible for the input to be exponential in the number of vertices without ever repeating a cycle. If the graph contains your example graph (2 and 3) as a subgraph, then it has cycles which are non-crossing and cycles which are crossing. As a result, you need to read the entire string to ensure you don't have any crossing cycles (which may or may not have been included). This takes time exponential in $n$ in the worst case.
Joe Fitzsimons
CC BY-SA 3.0
2012-05-24T20:40:25.580Z
@JoeFitzsimons: The input is just a sequence of points (i.e., pairs of real numbers), which need not be distinct.   The input size $n$ is the length of this sequence, _not_ the number of unique points.
Jeffε
CC BY-SA 3.0
2012-05-24T20:51:26.657Z
@Kaveh: Maybe too abstract/specialized?  Too many words?  I should have named the points [Ga, Ka, Naa, Taa, Tin, Khat](http://en.wikipedia.org/wiki/Bol_%28music%29)?
Jeffε
CC BY-SA 3.0
2012-05-25T08:37:27.223Z
@JɛﬀE: Ah I see. Sorry, I misunderstood how you were counting vertices.
Joe Fitzsimons
CC BY-SA 3.0
2012-05-30T15:43:31.210Z
@JɛﬀE: Can you explain your turning number a little more?  How do you determine if a vertex that turns 180 degrees contributes +1/2 or -1/2 to the turning number?
Pat Morin
CC BY-SA 3.0
2012-05-31T08:17:38.303Z
@PatMorin: I added some more detail.
Jeffε
CC BY-SA 3.0
2012-05-31T09:59:36.463Z
@Jeffe: I'm not an expert, but are there sequences of points that can be mapped both to a weakly simple polygon and to a non-self-crossing polygon with turning number >= 2 ? I'm thinking for example to the degenerate sequence: $(a \rightarrow b)^* \rightarrow a$. And if yes, how these cases must be treated?
Marzio De Biasi
CC BY-SA 3.0
2012-05-31T11:46:35.160Z
@MarzioDeBiasi: (A polygon _is_ a sequence of points; there is no mapping.)  I don't think so.  What I would like is is a definition of "modified turning number" that yields ±1 for any weakly simple polygon, just as the standard definition yields ±1 for simple polygons.  And I think of your particular example as zig-zagging on one "side" of the segment $ab$ rather than turning around it.
Jeffε
CC BY-SA 3.0
2014-07-09T20:52:58.063Z
(Warning: self-promotion detected.)  Jeff, Chao and I just released a manuscript ("[Detecting Weakly Simple Polygons](http://web.engr.illinois.edu/~hchang17/papers/pdf/wspolygon.pdf)") about this problem.  In short, [Cortese, Battista, Patrignani, and Pizzonia](http://www.sciencedirect.com/science/article/pii/S0012365X07010680) gave the first poly-time algorithm for the second problem, and we improved it to an $O(n^2\log n)$ time algorithm.  In Section A of our paper we also discussed several previous definitions on crossing and weak simplicity.
Hsien-Chih Chang 張顯之
<ds.algorithms><cg.comp-geom><polygon>
Detecting two kinds of almost-simple polygons
Jeffε
# Detecting two kinds of almost-simple polygons

(Asked by: username_0 on 2012-05-22)

I'm interested in the complexity of deciding whether a given non-simple polygon is *almost* simple, in either of two different formal senses: *weakly simple* or *non-self-crossing*. Since these terms are not widely known, let me start with some definitions.

* A **polygon** $P$ is the closed cycle of line segments connecting some finite sequence $p\_0, p\_1, p\_2, \dots, p\_{n-1}$ of points in the plane. The points $p\_i$ are called the *vertices* of the polygon, and the segments $p\_i p\_{i+1\bmod n}$ are called its *edges*. We can specify any polygon by just listing its vertices in order.
* A polygon is **simple** if all $n$ vertices are distinct and edges intersect only at their endpoints. Equivalently, a polygon is simple if it is homeomorphic to a circle and every edge has positive length. In general, however, the vertices and edges of a polygon may intersect arbitrarily, or even coincide.1
* Consider two polygonal paths $A$ and $B$ whose intersection is a common subpath of both (possibly a single point). We say that $A$ and $B$ **cross** if their endpoints $A(0), B(0), A(1), B(1)$ alternate on the boundary of a neighborhood of the common subpath $A\cap B$. A polygon is **self-crossing** if it has two crossing subpaths and **non-self-crossing** otherwise.2
* A polygon is **weakly simple** if it is the limit of a sequence of simple polygons, or equivalently, if there is an arbitrarily small perturbation of the vertices that makes the polygon simple. Every weakly simple polygon is non-self-crossing; however, some non-self-crossing polygons are *not* weakly simple.

For example, consider the six points $a,b,p,q,x,y$ shown below.

![enter image description here](https://i.sstatic.net/Wjs8f.png)

* The polygon $abpqyz$ is simple; see the left figure.
* The polygon $papbpqyqzq$ is weakly simple; the middle figure shows a nearby simple polygon. However, this polygon is not simple, because it visits $p$ three times.
* The polygon $papbpqzqyq$ is self-crossing, because the subpaths $bpqz$ and $yqpa$ cross. See the right figure for some intuition.
* Finally, the polygon $papbpqyqzqpapbpqyqzq$ (which winds twice around the middle polygon) is non-self-crossing, but it is *not* weakly simple. Intuitively, the [turning number](http://en.wikipedia.org/wiki/Winding_number#Turning_number) of this polygon is $\pm 2$, while the turning number of any simple polygon must be $\pm 1$. (A formal proof requires some case analysis, in part because the turning number is not actually well-defined for polygons with $0^\circ$ angles!)

> **Update (Sep 13):** In the figure below, the polygon $abcabcxyzxpqrxzyx$ is non-self-crossing **and has turning number 1**, but it is not weakly simple. The polygon arguably has several crossing *non-simple subwalks*, but it has no crossing *simple subpaths*. (I say "arguably" because it's unclear how to define when two non-simple walks cross!)
>
> ![enter image description here](https://i.sstatic.net/9R4hV.png)

So finally, here are my actual questions:

* **How quickly can we determine whether a given polygon is non-self-crossing?**
* **How quickly can we determine whether a given polygon is weakly simple?**

The first problem can be solved in $O(n^5)$ time as follows. Since there are $n$ vertices, there are $O(n^2)$ vertex-to-vertex subpaths; we can test whether any particular subpath is simple in $O(n^2)$ time (by brute force). For each pair of simple vertex-to-vertex subpaths, we can test whether they cross in $O(n)$ time. But this *can't* be the best possible algorithm.

I don't know whether the second problem can be solved in polynomial time. I think I can quickly compute a well-defined turning number for any non-simple polygon (unless the union of polygon edges is just a path, in which case the polygon must be weakly simple); see my answer below. **However, the new example polygon above implies that non-self-crossing and turning number 1 does *not* imply weakly simple.**

We can determine whether a given polygon is *simple* in $O(n^2)$ time by checking every pair of edges for intersection, or in $O(n\log n)$ time using a standard sweepline algorithm, or even in $O(n)$ time using Chazelle's triangulation algorithm. (If the input polygon is not simple, any triangulation algorithm will either throw an exception, infinite-loop, or produce output that is not a valid triangulation.) But none of these algorithms solve the problems I'm asking about.

---

1 Branko Grünbaum. [Polygons: Meister was right and Poinsot was wrong but prevailed](http://dx.doi.org/10.1007/s13366-011-0047-5). *Beiträge zur Algebra und Geometrie* 53(1):57–71, 2012.

2 See, for example: Erik D. Demaine and Joseph O'Rourke. [*Geometric Folding Algorithms: Linkages, Origami, Polyhedra*](http://gfalop.org/). Cambridge University Press, 2007.

**Tags:** ds.algorithms, cg.comp-geom, polygon
> **Comments:**
> **username_1**: I don't understand why one would down-vote this question?!  
> **username_2**: I may be totally misunderstanding the question, and so maybe this is way off, but it would seem to me that the way you count vertices means that the second question necessarily takes exponential time.  Let me explain: In your last example you use the same vertices multiple times. It seems easy to construct graphs where there is an exponential number of unique cycles.  
> **username_2**: If your input is the polygon given as in your examples, then it is possible for the input to be exponential in the number of vertices without ever repeating a cycle. If the graph contains your example graph (2 and 3) as a subgraph, then it has cycles which are non-crossing and cycles which are crossing. As a result, you need to read the entire string to ensure you don't have any crossing cycles (which may or may not have been included). This takes time exponential in $n$ in the worst case.  
> **username_0**: @JoeFitzsimons: The input is just a sequence of points (i.e., pairs of real numbers), which need not be distinct.   The input size $n$ is the length of this sequence, _not_ the number of unique points.  
> **username_0**: @Kaveh: Maybe too abstract/specialized?  Too many words?  I should have named the points [Ga, Ka, Naa, Taa, Tin, Khat](http://en.wikipedia.org/wiki/Bol_%28music%29)?  
> **username_2**: @JɛﬀE: Ah I see. Sorry, I misunderstood how you were counting vertices.  
> **username_3**: @JɛﬀE: Can you explain your turning number a little more?  How do you determine if a vertex that turns 180 degrees contributes +1/2 or -1/2 to the turning number?  
> **username_0**: @PatMorin: I added some more detail.  
> **username_4**: @Jeffe: I'm not an expert, but are there sequences of points that can be mapped both to a weakly simple polygon and to a non-self-crossing polygon with turning number >= 2 ? I'm thinking for example to the degenerate sequence: $(a \rightarrow b)^* \rightarrow a$. And if yes, how these cases must be treated?  
> **username_0**: @MarzioDeBiasi: (A polygon _is_ a sequence of points; there is no mapping.)  I don't think so.  What I would like is is a definition of "modified turning number" that yields ±1 for any weakly simple polygon, just as the standard definition yields ±1 for simple polygons.  And I think of your particular example as zig-zagging on one "side" of the segment $ab$ rather than turning around it.  
> **username_5**: (Warning: self-promotion detected.)  Jeff, Chao and I just released a manuscript ("[Detecting Weakly Simple Polygons](http://web.engr.illinois.edu/~hchang17/papers/pdf/wspolygon.pdf)") about this problem.  In short, [Cortese, Battista, Patrignani, and Pizzonia](http://www.sciencedirect.com/science/article/pii/S0012365X07010680) gave the first poly-time algorithm for the second problem, and we improved it to an $O(n^2\log n)$ time algorithm.  In Section A of our paper we also discussed several previous definitions on crossing and weak simplicity.  

---

## 2 answers

### Answer by username_0 on 2012-06-01. Score: 2

At Pat Morin's suggestion, here is my idea for computing the turning number. Sorry if this is a bit sloppy; I'm still fighting the notation demons. Moreover, Pat's comment to Chris's answer reveals that I've ignored some important degenerate cases. But I'll post this here anyway in case others find it useful.

For any index $i$, let $\theta(p\_i) = \theta(p\_{i-1}, p\_i, p\_{i+1})$ denote the *signed external angle* at vertex $p\_i$; this is the counterclockwise angle between the rays $\overrightarrow{p\_{i-1}p\_i}$ and $\overrightarrow{p\_ip\_{i+1}}$, normalized to the range $-\pi \le \theta\_i \le \pi$. (All index arithmetic is implicitly mod $n$.) The [*turning number*](http://en.wikipedia.org/wiki/Winding_number#Turning_number) of $P$ is defined as
$$
Turn(P) = \frac{1}{2\pi} \sum\_{i=0}^{n-1} \theta(p\_i).
$$
Let me call a vertex $p\_i$ a *spur* if the *internal* angle at $p\_i$ is equal to $0$. The external angle $\theta\_i$ at a spur is not well-defined; it could be either $\pi$ or $-\pi$. More generally, the turning number of $P$ is well-defined if and only if $P$ has no spurs (and no repeated vertices $p\_i=p\_{i+1}$). It's not hard to prove that $Turn(P)$ is an integer if it is well-defined; in particular, $Turn(P) = \pm 1$ if $P$ is a simple polygon.

Now suppose $P$ contains a walk of the form $p\mathord\to r\mathord\leadsto s\mathord\leadsto r\mathord\to q$, where $p\ne q$ and the path $r\mathord\leadsto s$ is the reversal of the path $s\mathord\leadsto r$. Then $s$ is a spur; call $r$ the *root* of $s$. In this case, let me *define* the external angle at $s$ as follows:
$$
\tilde\theta(s) = \pi \cdot \mathop{sgn}\theta(p, r, q) =
\begin{cases}
\pi & \text{if } \theta(p, r, q) > 0\\
-\pi & \text{if } \theta(p, r, q) < 0
\end{cases}
$$
**(But what if $\theta(p,r,q)=0$? As Pat observes, this can actually happen. Probably there's some sort of recursive way to define $\tilde\theta(s)$ even in this case, but I don't know what it is.)**

If $P$ is weakly simple, then there is a simple $n$-gon $\tilde{P}$ arbitrarily close to $P$; tet $\tilde{s}$ be the vertex of $\tilde{P}$ closest to $P$. As $\tilde{P}$ approaches $P$, the internal angle at $\tilde{s}$ approaches zero. It's not hard to prove (by induction on the length of $r\mathord\leadsto s$) that the external angle $\theta(\tilde{s})$ approaches $\tilde\theta(s)$.

If $P$ consists entirely of a walk followed by its reversal, $r\mathord\leadsto s\mathord\leadsto r$, then the external angles at the spurs $r$ and $s$ are still not well-defined. But in this case, I believe $P$ is weakly simple if and only if the walk $r\mathord\leadsto s$ is non-self-crossing. **(There are more complex cases where I cannot define a reasonable modified turning number, in particular, if the polygon wanders back and forth through a single walk. But in all such cases, it appears that the polygon is weakly simple if and only if it is non-self-crossing.)**

Otherwise, if we define $\tilde\theta(p\_i) = \theta(p\_i)$ for any non-spur vertex $p\_i$, we now have a well-defined turning number $\widetilde{Turn}(P) = \sum\_i\tilde\theta(p\_i)/2\pi = Turn(\tilde{P})$, which must be $\pm 1$ if $P$ is weakly simple.

I'm no longer confident that $\widetilde{Turn}(P)$ can be computed in linear time. The main difficulty is that the walk $r\mathord\leadsto s$ can itself contain spurs. The naive algorithm that finds the root of each spur by brute force actually takes $\Theta(n^2)$ time in the worst case; consider an $n$-gon that has a subwalk of length $\Omega(n)$ that simply alternates between two points.


---

### Answer by username_6 on 2012-05-26. Score: 2

It seems like the first question has a $O(n^3)$ algorithm (though this is also likely not optimal). Assuming that there is a crossing, the key to finding it seems to be that the edges that must be found are those immediately on either side of the common subpath. Therefore, we look at all pairs of consecutive pairs of edges. There are a quadratic number of these. If we find a pair of pairs of edges with vertices $abc$ and $def$ such that edges $bc$ and $ef$ are the same, then we follow the common subpath to the end and inspect the edges that leave it. If they form a crossing along with $ab$ and $de$, then we are done, otherwise we go on to the next pair. Following the common subpath is at most a linear-time operation, so the whole algorithm is $O(n^3)$.

This analysis probably isn't tight since the number of times a linear-length common subpath will be followed isn't linear in the number of pairs of pairs. There should be only a constant number of those. Similarly, if the length of the longest common subpath is constant, then we are okay in terms of the amount of time following common subpaths. I would expect that the worst case arises when there is a single subpath of length $O(\sqrt{n})$ that is common to $O(\sqrt{n})$ subpaths. Then there are $O(n)$ interactions and in each interaction $O(\sqrt{n})$ edges are being followed. So even still, the number of edges that are followed is $o(n^2)$, and the bound is provided by the number of pairs. Thus I would guess that the true bound for this algorithm is $O(n^2)$.

> **Comments:**
> **username_3**: "Following the common subpath is at most a linear-time operation..."  Is this true?  Remember that the subpaths are not identical.  One may be folding back and forth along the image of the other.  In fact, it's not even clear (to me) when you know you're done.  
> **username_6**: Good point.  Would it be possible, as a preprocessing step, to put the polygon in some kind of standard form?  We would elide paths that immediately fold back on themselves, as well as vertices that are collinear with their immediate neighbors.  Then the sentence that you quoted would be better defined -- the common subpath consists of edges that have the same vertices, and you know that you are done because you hit different vertices.  Proving that the answer remains the same in the polygon in standard form should not be too hard.  
> **username_0**: @ChrisGray: Maybe, but not quite as easily as you've suggested.  If the image of $P$ is a tree, then recursively eliding _all_ switchbacks eventually reduces $P$ to a single point.  
> **username_6**: Yes, you're right, that idea won't work.  The rightmost figure you gave above would be reduced to a single point.  
> **username_0**: I'm plan to let the bounty expire; half the points will be automatically awarded to this answer.  

---

