Page 289 - Sensing, Intelligence, Motion : How Robots and Humans Move in an Unstructured World

264 MOTION PLANNING FOR TWO-DIMENSIONAL ARM MANIPULATORS

1
Proof: If this were not so, the component of C containing x would have, by
Theorem 5.9.4, the single vertex x as its boundary. This is contrary to Theo-
rem 5.9.3. Q.E.D.

2
2
2
Theorem 5.9.6. [110, V.3.3] For any C , ∂|C |=|∂C |.
2
It follows from Theorem 5.9.6 that and 0 are the only 2-cycles. Hence, if ∂C 2
2
2
2
is connected then so is C , because either C = or else every component of
2
2
2
C contains a non-null component of ∂C . On the other hand, if C is connected,
2
it does not necessarily mean ∂C is connected.
∗
It is sometimes necessary to pass from one grating, G, to another, G ,by
∗
introducing additional lines. Such a new grating G is called a refinement of
the old. (It is convenient to agree that G is a refinement of itself.) A common
refinement can be formed for any two gratings G 1 and G 2 , by taking all the lines
of G 1 and G 2 as cross lines.
k
k
To each k-chain, C on G corresponds to the subdivided k-chain C on G ;
∗
∗
k
k
C is the sum of the k-chains into which the k-chain C are subdivided. (0-chains
∗
0
0
are unaltered by subdivision: C = C .) A subdivided chain has the same locus
∗
k
k
as its original: |C |=|C |.
∗
Theorem 5.9.7. [110, V.4.1]
k
k
k
k
k
(C + C ) ∗ = C k 1∗ + C , (∂C ) ∗ = ∂(C )
2
1
2∗
∗
k
k
Corollary 5.9.1. C is a k-cycle if and only if C is a k-cycle.
∗
1 k
Separation Theorems. Let E be an open set of T ,and let be a k-cycle on
k
k
a grating G defined in E.We say the cycle bounds in E, denoted as ∼ 0, if
there is, on some refinement G of G,a (k + 1)-chain C k+1 such that |C k+1 |⊆ E
∗
k
k
k
k
and ∂C k+1 = on G .Wesay is nonbounding in E if | |⊆ E but does
∗
not bound in E. The notion of bounding can be used to study the connectivity of
1
a subset of T : A simple closed curve (a 1-cycle) bounds if it separates a subset
from the rest of the space; if two vertices (a 0-cycle) in G do not bound in E,
then E is not connected.
By Jordan Curve Theorem [110, V.10.2], a simple closed curve always bounds
in a plane (a sphere). The following statement indicates this is not necessarily
true in a torus.
1
Theorem 5.9.8. Every 1-cycle on a rectangular grating in T is the boundary of
either none 2-chain or just two 2-chains.
Proof: The proof is by induction on the number of lines drawn across the unit
1
square that represents T . On the grating consisting of a and b alone, the only
2
1-cycles are (a) the null sets, which bound two 2-chains (the zero chain and ),
and (b) the cycles a, b,and a + b, each of which does not bound (i.e, does not