3
$\begingroup$

Show that any closed polygonal path can be decomposed into a finite union of simple closed polygonal paths and line segments traversed twice in opposite directions.

MY SOLUTION

Suppose $\gamma(t):a\leq t\leq b$ has $\gamma (t_{2}) = \gamma (t_{1})$. Then $\gamma$ can be written as a union of $\gamma_{1}$ and $\gamma_{2}$ where $\gamma_{1}=\gamma(t); t\in[a,t_{1}]\bigcup[t_{2},b]$ and $\gamma_{2}=\gamma(t)$; $t\in[t_{1}, t_{2}]$.

Is correct my method?

  • 1
    I don't see what you are trying to claim in your approach. Read the question again, carefully. Try to draw a few increasingly more complicated closed polygonal paths, in particular non-simple ones and see if you can come up with an idea.2012-05-02

1 Answers 1

2

I’ll put down some specific definitions and then prove the result .........

Definition: a closed polygonal path (hereafter, a polygon) comprises a finite sequence of directed finite straight lines called edges $(E_i)_{i = 1, n}$ where consecutive (and the last and first) edges connect at their endpoints. In total, the edges form a closed directed path in space. These connection points are called vertices and the vertex where $E_i$ and $E_{i+1}$ connect is labelled $V_{i+1}$: the vertex where $E_n$ and $E_1$ connect is labelled $V_1$.
Note: the definition here is wide and permits edges to be “in line” i.e. two edges to meet at an angle of 180 degrees, allows edges to intersect and overlap, and allows non-consecutive vertices at the same point in space. A sequence of edges (rather than a set) allows for the possibility that two or more edges duplicate the same path in space. A polygon can also be defined by a sequence of vertices, but the edge definition is more useful in what follows.
A bigon is a (degenerate) polygon having only two edges and its path is a straight line traversed in opposite directions.
(A monogon is sometimes defined as a degenerate polygon with one vertex. It is to be understood here that all polygons have two or more vertices).

Definition: an intersection in a polygon occurs if two non-consecutive edges cross or overlap, or two consecutive edges overlap other than at their common vertex. To avoid duplication, consider only $1 \le i \lt j \le n$. More formally $E_i, E_j$ intersect if $E_i \cap E_j \ne \emptyset$ and $(j \ne i + 1$ or $E_i \cap E_j \ne V_{i+1})$.
From the geometry of straight lines, two edges are either parallel or they aren’t and can only intersect in one of the following three ways:
Point intersection: two non-parallel edges cross or meet at a single point (other than consecutive edges at their common vertex).
Parallel overlap: two parallel edges overlap in the same direction.
Bigon overlap: two parallel edges overlap in opposite directions.
Observe
• With this definition, any two edges can only intersect once and the number of intersections in an n-edge polygon is therefore finite, being limited combinatorially to $(n – 1) !$ and geometrically to less.
• Several edges could satisfy a “higher order” intersection $E_i \cap E_j \cap E_k ......... \ne \emptyset$ which according to this definition would be represented as a number of pairwise intersections $E_i \cap E_j, E_i \cap E_k, .....$ Clearly a polygon with no pairwise intersections has no higher order intersections either.

Definition: a simple polygon is one with no intersections. It follows from the definitions so far that a simple polygon is not a bigon.

Definition: a single refinement of a polygon P with $n$ edges to a polygon P’ with $n + 1$ is the splitting of an edge, say $E_i$, at a point strictly between its endpoints into two consecutive edges $E_{i_1}$ and $E_{i_2}$, connected by a vertex at the chosen point and resulting in the same closed directed path round the polygon. The edges and vertices of the polygon P’ may then be renumbered $1$ to $n+1$.

Definition: A refinement of a polygon P to a polygon P’ is the result of a finite number of single refinements. Clearly, for a given collection of single refinements (i.e. making a finite number of splits in the edges) the refinement P’ is independent of the sequence in which the single refinements are applied.

Definition: two different finite sequences of polygons $\mathscr P_A = (P_{A_1}, P_{A_2}, ...)$ and $\mathscr P_B = (P_{B_1}, P_{B_2}, ...)$ are equivalent if they have the same directed edges up to refinement. More formally, $\mathscr P_A ≈ \mathscr P_B$, if there are refinements of some or all the polygons in either or both sequences such that there is a bijection between all the edges in $\mathscr P_A$ and $\mathscr P_B$ where the matched edges represent the same spatial paths. (Again, sequences are considered rather than sets to allow for spatial duplication).

Because the result of refinements is independent of sequence it follows that if $\mathscr P_A ≈ \mathscr P_B$ and $\mathscr P_B ≈ \mathscr P_C$ then taking all the single refinements and applying them to $\mathscr P_A$ gives $\mathscr P_C$. So $\mathscr P_A ≈ \mathscr P_B$ and $\mathscr P_B ≈ \mathscr P_C$$\mathscr P_A ≈ \mathscr P_C$ i.e. the relation ≈ is transitive. (Only transitivity matters here, but in fact, ≈ is an equivalence relation on sequences of polygons clearly $\mathscr P_A ≈ \mathscr P_A$ (symmetric) and $\mathscr P_A ≈ \mathscr P_B ⇒ \mathscr P_B \implies \mathscr P_A$ (reflexive)).

LEMMA: any polygon is equivalent to a finite number of simple polygons and bigons.
Note: different simple polygons or bigons in the representation are allowed to intersect each other.
Proof:
The essence of the proof is to remove intersections one by one. Each removal creates a new sequence of polygons and bigons which are equivalent to the previous sequence. No new intersections are created in the process. So there being a finite number of intersections to begin with, they are all removed after a finite number of steps. Transitivity then ensures that the final sequence of simple polygons and bigons is equivalent to the original polygon. It remains to demonstrate how intersections are removed....

The diagrams that follow are illustrative - the proof is analytic.

Removing a point intersection.

For a polygon P with n edges, for simplicity consider the numbering such that the intersection is between $E_1$ and $E_i$ with $2 \lt i \lt n$. (By geometry, $E_2$ and $E_n$ cannot have point intersections with $E_1$, only overlaps).

enter image description here

Firstly, refine the polygon P if necessary and call the new polygon P’. By definition, P’ is equivalent to P.
• If the intersection is not at a vertex of $E_i$ then split $E_i$ at the intersection point.
• If the intersection is not at a vertex of $E_1$ then split $E_1$ at the intersection point.
According to the definition this will create additional pairwise intersections, but they and the original intersection will all be removed in what follows. Refinement would change the numbering so that the intersection is now between $E_1$ and Ej where $j = i, i+1, i + 2$ depending on which refinements were performed and P’ has $m = n, n+1, n + 2$ edges .

Now, after any refinements the intersection between $E_1$ and $E_j$ is the spatial relationship $V_2$ = $V_j$

enter image description here

The edges $E_1$, $E_j$ are part of the directed connected path of the polygon P’ and $1 < j < m$, so there must be a sequence of edges $\mathscr E_A$ connecting $E_1$ to $E_j$ and another $\mathscr E_B$ connecting $E_j$ back to $E_1$.

enter image description here

But now $\mathscr E_A$ starts and ends at the point $V_2 = V_j$ and so forms a polygon $P_A$, and the sequence of edges $(E_1, E_j, \mathscr E_B)$ forms a polygon $P_B$.

The two polygons $P_A$ and $P_B$ exactly contain all the directed edges of P’ so ($P_A$, $P_B$) is equivalent to P’ and by transitivity is equivalent to P.
Then $E_1$ and $E_j$ (after re-numbering) are now consecutive edges in $P_A$ so their common vertex is no longer an intersection and there is at least one less intersection in ($P_A$, $P_B$) than in P.
(Note: any additional intersections introduced during refinement were between edges now in different polygons, or $E_2$ and $E_{j-1}$ which are now consecutive in $P_B$. So any additional intersections have been removed).  

Removing a parallel intersection.

Two parallel edges, overlap in the same direction. For simplicity assume $E_1$ and $E_i$. (In the diagrams the edges are shown slightly separated for clarity).

enter image description here

Firstly, refine the polygon P if necessary and call the new polygon P’. By definition, P’ is equivalent to P.
• if $V_2$ is between $V_i$ and $V_{i+1}$ split $E_i$ at $V_2$
• if $V_1$ is between $V_i$ and $V_{i+1}$ split $E_i$ at $V_1$
• if $V_{i+1}$ is between $V_1$ and $V_2$ split $E_1$ at $V_{i+1}$
• if $V_i$ is between $V_1$ and $V_2$ split $E_1$ at $V_j$

After any renumbering, the intersection is between $E_1$ and $E_j$ with $ j = 1, i+1, i+2$ which now have spatially co-incident vertices $V_1 = V_j$ and $V_2 = V_{j+1}$ The polygonal path is connected and there must therefore be a sequence of edges $\mathscr E_A$ connecting $E_1$ to $E_j$, and likewise $\mathscr E_B$ connecting $E_j$ to $E_1$.

enter image description here

Then the sequence of edges $(E_j, \mathscr E_A)$ is a polygon $P_A$, as is $(E_1, \mathscr E_B)$ a polygon $P_B$.
($P_A$, $P_B$) is equivalent to P and $E_1, E_j$ now being in separate polygons no longer intersect. So there is at least one less intersection in ($P_A$, $P_B$) than in P.

Separate a bigon intersection (“let bigons be bygones”).

Following the same refinement as for parallel intersections we can assume a bigon intersection between $E_1$ and $E_j$ with co-incident vertices. If $(E_1, E_j)$ is the entire polygon there is nothing further to do. Otherwise there are edges $\mathscr E_A$ connecting $E_1$ to $E_j$ and/or $\mathscr E_B$ connecting $E_j$ to $E_1$.

enter image description here

Then $(E_1, E_j)$ is a bigon, and the non-empty $\mathscr E_A$ and/or $\mathscr E_B$ are polygons, in total being equivalent to P with at least one less intersection.