Kurt Mehlhorn. # Constructive Hopf's theorem: or how to untangle closed planar curves online

. **(page 1 of 2)**

Online Library → Kurt Mehlhorn → Constructive Hopf's theorem: or how to untangle closed planar curves → online text (page 1 of 2)

Font size

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

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 2

Online Library → Kurt Mehlhorn → Constructive Hopf's theorem: or how to untangle closed planar curves → online text (page 1 of 2)