Copyright
Kurt Mehlhorn.

Constructive Hopf's theorem: or how to untangle closed planar curves online

. (page 1 of 2)
Online LibraryKurt MehlhornConstructive Hopf's theorem: or how to untangle closed planar curves → online text (page 1 of 2)
Font size
QR-code for this ebook


Robotics Research
l^hnical Report




Constructive Hopf's theorem: or how to untangle
closed planar curves

by

K. Melhorn, C. Yap
A

Technical Report No. 340

Robotics Report No. 134

January, 1988




^ . '*'V*






S55S;-^a;lii»^?15i.,-ir,, then fl' is either equal to

< D,, ...,t;„,ui,...,D,_i,v,- >

for some i = 1, . . . , n, or the reverse of this sequence. A polygon P on n vertices is defined as the
combinatorial equivalence class of some closed path Fl =< vi,...,Vn,vi >. We will express the
polygon as

P = (vi,...,v„).

So P can also be written as {vj,V3, . . . ,v„,vi), say. For this paper, we further require that
polygons satisfy the following local condition:

(C) For any consecutive triple v,_i, r,, ii, + i, if the three vertices are collinear, then
V, lies strictly between the other two,

t;, = avi-i + (I - a)u,+i

for some < Q < 1.

(Here, as throughout the paper, arithmetic on indices of vertices of a polygon P is modulo n,
the length of the sequence P.) Note that (C) in particular prevents Vi = Vj for |i — _7| = 1 or 2.
However, we allow v, = Vj for |t — y| > 2 and in fact edges may even coincide. The reason for (C)
is that the equivalence we seek allows local transformations that do not create kinks, and if (C)
fails then it sometimes becomes ambiguous whether a kink is introduced.

The transformations we allow are of three types:

(TO) Insertion. We may transform P = {vi,...,Vn) to

Q = (ui,...,t;,,u,t;, + i,...,t;„),(» = l,...,n)

where u is a point lying strictly between d, and v,+i.
(Tl) Deletion. We may transform P = (ui,.. . , v„) to

Q = (vi,...,u,-i,u,>i,...,v„),(t = l,...,n)



2 CLASSIFICATION OF POLYGONS 4

provided tt,_i, t),, t;,-(-| are collinear.

To introduce the last type of transformation, we need a definition. Relative to any vertex
V,, we define two forbidden cones (at v,_i and fi+i, respectively): the forbidden cone at d,_i is
bounded by the two rays emanating from Vi-i, one ray directed towards v,_2 and the other directed
away from Vi+i. Of the two choices of cones bounded by these rays, we choose the one that does
not contain v,-. The forbidden cone at Vi+i is similarly defined, being bounded by the two rays
emanating from D,^-t and directed towards v,^2 ^tid away from v,-i, respectively. Each cone is a
closed region so it includes the bounding rays. This definition applies for all n > 3. We are now
ready for the third transformation type.

v.-







Figure 2. Forbidden cones



(T2) Translation. We may transform P = (i'i,...,fn) to

Q = (t),,...,v,-i,u,D,+i,...,v„),(i = l,...,n)

where u is any noint not in the union of the two forbidden cones of u,. In otherwords, we replace
the point u, by u.

Definition: We say that two polygons P,Q are equivalent if one can be transformed to the
other by a finite sequence of operations of types T0,T1,T2.

It is not hard to see that the relation is a true equivalence relation. Of course, we know from
Hopf's theorem (applied to polygons) that it is sufficient to look at the winding number of a poly-
gon. However, given two equivalent polygons P and Q, it is unclear how one can

(A) transform P into Q by a sequence of (T0-T2) transformations,

(B) bound the number of transformation steps needed, and

(C) give an efi^icicnt algorithm to find a sequence of such transformation steps.

Indeed, standard proofs of Hopf's theorem yield no constructive information to answer these ques-
tions.

We answer these questions (A-C) by defining a unique normal form (i.e. representative) of each
equivaJcnce class, and showing that a quadratic number of steps suffices to reduce a polygon into
the normal form. The algorithm to find these steps runs in linear time. In particular, this solves
the problem of transforming between two equivalent polygons P,Q since the normal form is unique
and the steps are reversible: first convert P to the normal form and then reverse the steps from
the normal form to Q.



3 STAR POLYGONS



To think about what might be desirable, we note (see Fig. 3) that the triangle and the bow-tie
are obvious candidates for normal forms. Perhaps less convincingly, the 5-point star (5-8tar) also
seems like a good candidate for a normal form.




x




Figure 3. The triangle, bowtie and 5-star

The next figure illustrates a sequence of transformations to reduce a Victoria Cross polygon to
one with fewer vertices.




SUps




Figure 4. Reduction of the Victoria Cross



Remark. Any smooth closed curve can be approximated by a polygon and the transformations
can discrctized as a series of our (TO-2) transformations. So in some sense we have also solved the
corresponding question for smooth curves.



3 Star Polygons

DeBnitlon: A polygon is reductble if it is equivalent to one with fewer vertices. It is irreductble
otherwise.

One can check that the triangle, bow-tie and 5-star cannot be transformed by (Tl) or (T2)
transformations into any polygon with fewer vertices. But it turns out that even with (TO) trans-
formations (which insert new vertices) the result is true: these are irreducible polygons. Since they
have different number of vertices, it follows that they are inequivalent to each other. (Of course we
can conclude this at once if we apply Ilopf's theorem.) In fact, all polygons on 3, 4 and 5 vertices
are equivalent to these three candidates using only (T2) transformations. One may also check that
there are no irreducible polygons on 6 vertices!



3 STAR POLYGONS

The 5-3tar is also equivalent to the polygons in Fig. 5.






Figure 5. Polygons equivalent to the 5-star: the Fox, the Rabbit and Radioactive Sign

Note that the first polygon in Fig. 5 has the minimal number of self- intersections among its
equivalence class, so perhaps it is a better choice of a normal form than the 5-8tar. This indicates
that the choice of a good normal form is not obvious. Our first result, though simple, helps to
narrow our choices considerably.

Theorem 1 Every polygon P can he transformed by (T2) transformations into a polygon Q all of
whose vertices are disltiict and he on a circle.

Proof. Let C be a circle that contains all the vertices of F in its interior. For each vertex v of P,
we may move v onto C using a (T2) transformation: this follows from the observation that the
non-forbidden region relative to v always contain an infinite cone K at i». We may move v in any
direction inside K until we reach C. Furthermore, we can make sure that we avoid any vertex
already on C. Q.E.D.

Henceforth, wc assume that polygons have their vertices on some circle. Among the polygons
on a circle, wc define a particularly nice class.

Definition: A path II =< vi,...,v„ > is called a star path if the edges e, = lu,,t^i-n] (for each
I = 1 , . . . , n - 1) intersect each of the edges

ei,e2,...,c,-i.

Here the edges are closed line segments and so c, (t > 2) always intersects e,-i. A polygon
P = (ui, . . . , Vn) is called an n-slar if for some choice of an initial vertex v,, t = I, . . . , n, the path

n, =< Vi,...,Vn,Vl,...,Vi-i >

is a star path.

This terminology agrees with what we had called the 5-star before. The triangle is a 3-star and
the bow-tie a 4-star. The following figure shows the next few n-stars.



4 A CANONICAL FORM FOR POLYGONS






Figure 6. 6-, 7-, and 8-stars



The following lemma is easy:



Lemma 2

1. For n = 4 or for odd values of n, if a polygon P = (ui,. . . ,Un) is an n-siar then for every choice

of intlial vertex v,, the path Fl, =< Vi,...,v„,v\ r,-i > is o star path. (In other words, the

definition of a n-star does not depend on the choice of the initial vertex in these cases.)

2. For all other cases of n, there is a unique choice of an initial vertex v, which makes 0, a star
path.

Lemma 3 Let n, m be odd positive integers or equal to 4- If n jt m, then the n-star and the m-star
are inequivalent.

Proof. One checlcs that the winding number of the 4-star is and for each positive integer k, the
{2k -f l)-star has winding number ±2kn (where the sign corresponds to a choice direction for the
polygon). The result then follows from the fact that the winding number of a polygon is unchanged
by any transformation of types (TO-2). Q.E.D.

This lemma supplies us with an infinite list of inequivalent polygons. We next prove that this
list exhausts all the equivalence classes.



4 A Canonical Form for Polygons

We now set out to prove

Theorem 4 (Canonical Form) Every polygon can be transformed by a sequence of (Tl) and
(TS) transformations into an n-star, for some n that is either odd or equal to 4-

Corollary 5 An n-star is irreducible if and only if n = A or n is odd.

Proof. Suppose that an n-star is irreducible. Then the theorem implies that n must be 4 or odd.
Conversely, let n = 4 or odd. If an n-star is reducible, then the theorem shows that it is reducible
to an m-star for some m < n where m = 4 or odd. This contradicts the previous lemma that the
n- and m-stars are inequivalent. Q.E.D.



4 A CANONICAL FORM FOR POLYGONS



We prove the canonical form theorem by a sequence of lemmas.

A polygon that can (resp. cannot) be transformed to one with fewer vertices using just (Tl)
and (T2) transformations will be called semt-reductble (resp. serm-irreductble).

We need a useful notation. Henceforth, we write only the indices (i.e. subscripts) of vertices
to denote the vertices. So we write F = (1, 2, . . . , n) for n > 3. Next, if ui, U2, . . . , ujt (^ > 3) are
indices (not necessarily consecutive) we shall write

ui < U2 < ••• < ujt

to mean that as we traverse the circle of P in a clockwise direction, starting from ui, we will meet
the indices U|, U2, . . . , Ujt in this order.

The following simple fact is very useful:

Lemrua 6 Suppose P = (l,...,n) (n > A) is such that the pair of edges [1,2] and [3,4] do not
intersect, and also the pair [2, 3] and [A, 5] do not intersect. Then P 15 equivalent to (1, 2, 4, 5, ... , n)
by a (Tl) transformation. In other words, we may delete index S.





4- i




Figure 7. Can delete index 3

This is the only form of deletion of vertices used in our proof. Henceforth, whenever we delete
vertices it is by appeal to this lemma.

We say that P = ( 1 , 2, . . . , n) conjoins an N-shape if n > 4 and for some choice of index «", we
have

i < t ■+ 1 < I + 3 < i + 2



or



t < »■ + 2 < I + 3 < t ■+ 1.



4 A CANONICAL FORM FOR POLYGONS




t+a




Figure 8. An N-shape

Lemma 7 A aemt-trreducible polygon P = (1,2 n) does not contain an N-shape unless n = 4.

Proof. By way of contradiction, assume P has an N-shape. By symmetry, assume 1 < 2 < 4 < 3.



n 6




{?)




Figure 9. Reduction of an N-shape




The result is true for n = 4, so suppose n > 5. Since P is semi-irreducible, by the previous
lemma, the edge [4, 5] must intersect [2, 3]; hence 3 < 5 < 2. Similarly, 2 < n < 3. This shows that
n 51^ 5 so assume ti>6. Ifl 6. By the previous lemma, we know
that P does not contain an N-shape. Suppose indices (2,3,4,5) forms a U-shape as in the figure,
2 < 5 < 4 < 3.





Figure 11. The elimination of U-shape

Since index 3 cannot be deleted, we have 4 < 1 < 3, and similarly, since index 4 cannot be
deleted, 4 < 6 < 3. Suppose the relative position of indices 1 and 6 satisfies

4 < 1 6. If v = 7 then (4,5,6,7) forms an N-shape which is a contradiction. If w = 8
then note that v— l


1

Online LibraryKurt MehlhornConstructive Hopf's theorem: or how to untangle closed planar curves → online text (page 1 of 2)