22
$\begingroup$

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

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

enter image description here

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. 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. Cambridge University Press, 2007.

$\endgroup$
  • $\begingroup$ I don't understand why one would down-vote this question?! $\endgroup$ – Kaveh May 24 '12 at 18:22
  • $\begingroup$ 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. $\endgroup$ – Joe Fitzsimons May 24 '12 at 18:50
  • $\begingroup$ 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. $\endgroup$ – Joe Fitzsimons May 24 '12 at 18:52
  • 1
    $\begingroup$ @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. $\endgroup$ – Jeffε May 24 '12 at 20:40
  • 2
    $\begingroup$ @Kaveh: Maybe too abstract/specialized? Too many words? I should have named the points Ga, Ka, Naa, Taa, Tin, Khat? $\endgroup$ – Jeffε May 24 '12 at 20:51
2
+125
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ "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. $\endgroup$ – Pat Morin May 30 '12 at 15:41
  • $\begingroup$ 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. $\endgroup$ – Chris Gray May 31 '12 at 1:35
  • $\begingroup$ @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. $\endgroup$ – Jeffε May 31 '12 at 8:31
  • $\begingroup$ Yes, you're right, that idea won't work. The rightmost figure you gave above would be reduced to a single point. $\endgroup$ – Chris Gray May 31 '12 at 22:55
  • $\begingroup$ I'm plan to let the bounty expire; half the points will be automatically awarded to this answer. $\endgroup$ – Jeffε Jun 1 '12 at 6:56
2
$\begingroup$

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.

$\endgroup$

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.