Detecting two kinds of almost-simple polygons

Question

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

• 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.²

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

• 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 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!)

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.

---

¹ Branko Grünbaum. Polygons: Meister was right and Poinsot was wrong but prevailed. Beiträge zur Algebra und Geometrie 53(1):57–71, 2012.

² See, for example: Erik D. Demaine and Joseph O'Rourke. Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press, 2007.

Answer 1

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

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