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

APPENDIX 265

1
separate a region from T ) because there is only one rectangle in the grating,
which is and ∂ = 0.
Assume the given grating, G 1 , is formed from a grating G 0 , for which the
theorem holds true, by the addition of a line λ across the square; assume λ is
1
2
parallel to a.Let be the given 1-cycle on G 1 .Wedenoteby C the sum of
1
the 2-cells of G 1 whose lower edges lie in the line λ and belong to .The
1
2
1-cycle + ∂C therefore contains no edge in λ. It follows that this 1-cycle
1
1
2
is the subdivided form of a 1-cycle on G 0 , because + ∂C contains no
0
horizontal edge at a vertex x of λ and therefore, since it is a cycle, contains both
or neither of the vertical edges at x, which together make up an edge of G 0 .
2
By hypothesis, if F 0 1 bounds, then there is a 2-chain C on G 0 such that
0
2
1
2
1
2
2
2
= ∂C ; and, if C is the subdivided form of C on G 1 ,then ∂C = + ∂C .
0 0 1 0 1
Hence by Theorem 5.9.2
2
2
1
2
2
∂(C + C ) = ( + ∂C ) + ∂C = 1
1
2
1
2
2 −1
The 2-chain (C + C ) also has boundary .
1
1
1
For every 1-cycle in G 0 there is a 1-cycle in G 1 , which is the subdivided
0 1
1
form, or a refinement, of . Therefore, by Corollary 5.9.1, if every 1-cycle in
0
G 1 bounds, so will every 1-cycle in G 0 , which is impossible.
1
It has thus been shown that bounds none or two 2-chains. No 1-cycle
2
2
2
2
bounds more than two 2-chains. For if ∂C = ∂C ,then ∂(C + C ) = 0and
a b a b
2 −1
2
2
2
2
therefore C + C is 0 or ,i.e. C = C or (C ) . Q.E.D.
a
a
a
b
b
1
1
1
Theorem 5.9.9. [110, V.6.4] If 1-cycles and bound in T , and x and y do
2
1
1
1
1
1
1
1
not lie on | | or | |, at least one of the 1-cycles , , + bounds in
1 2 1 2 1 2
1
T − (x ∪ y).
1
Theorem 5.9.10. [110, V.9.1.2] Let F 1 and F 2 be closed sets in T . If the points
x and y bound the 1-chain k i not meeting F i (for i = 1, 2) and if k 1 + k 2 ∼ 0 in
1
T − F 1 F 2 ,then x and y are not separated by F 1 ∪ F 2 .
1
Theorem 5.9.11. [110, V.10.1] A simple arc in T has a single complementary
region.
1
For a region D in T ,a simple arc L, with one endpoint on ∂D and all its other
points in D, is called an end-cut. If both endpoints are on ∂D and the rest in
D,the arc is a cross-cut.
1
Theorem 5.9.12. Given a region D of T , a cross-cut L can be drawn in D such
that both endpoints of L in D are on the same component of ∂D,(D-L) has two
components, and L is contained in the boundary of both.
Proof: First we prove that for any cross-cut L in D, (D − L) has at most two
components. Let u and v be the two endpoints of L. Suppose x, y, z are points