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

266 MOTION PLANNING FOR TWO-DIMENSIONAL ARM MANIPULATORS

of three different regions of D − L. By Theorem 5.9.11, there exists a 1-chain
k 1 bounded by x and y, such that k 1 does not meet L; and by hypothesis, there
exists a 1-chain k 2 bounded by x and y, such that k 1 does not meet D −1 ,the
1
complement of D in T .Since x and y are separated by L ∪ D −1 , it follows
from Theorem 5.9.10 that k 1 + k 2 is nonbounding in (LD −1 −1 1
) ,thatis, in T −
(u ∪ v).
Similarly, (y) + (z) is the common boundary of two 1-chains k 3 and k 4 that do
1
not meet L and D −1 respectively, and k 3 + k 4 is nonbounding in T − (u ∪ v).
Therefore, by Theorem 5.9.9,
1
(k 1 + k 2 ) + (k 3 + k 4 ) ∼ 0 in T − (u ∪ v) (5.9)

The 1-chain k 1 + k 3 does not meet L and is bounded by (x + y) + (y + z)—that
is, by x and z. Similarly, k 2 + k 4 does not meet D −1 and is bounded by x and
z.The sum

(k 1 + k 3 ) + (k 2 + k 4 )

is identical to (5.9) and therefore bounds in (LD −1 −1
) . Hence, x and z are not
bounded by L ∪ D −1 , contrary to the hypothesis.
Nowweshow thatacross-cut L can be drawn in D such that (D − L) has
at least two components. Consider one component, F,of ∂D and assume that
1
it contains at least two points, u and v. Define a grating G on T such that no
2-cells meet more than one component of D or D −1 (Theorem 5.9.1), and that
both u and v are vertices of G.Let K be the set of 2-cells in G that meet F.
Then, ∂K bounds at least two regions; one contains F and the others do not.
Let κ 1 be 1-chain such that |κ 1 |=|∂K|∩ D and let κ 2 be 1-chain such that
|κ 2 |=|∂K|∩ D −1 . Clearly, |κ 1 | and |κ 2 | are disjoint. Thus, D −|κ 1 | separates
D into at least two components. Since u ∈ F is a vertex in G, one of the four
1-cells adjacent to u must have its other vertex in κ 1 . Denote the 1-cell that
1
1
connects u and κ 1 by C , denote the 1-cell that connects v and κ 1 by C ,and let
1 2
1
1
L be the locus of any 1-chain in C + C + κ 1 bounded by u and v. (D − L)
1 2
has at least two components. Q.E.D.
A point of ∂D is accessible from D if it is an endpoint of an end-cut in D.
Theorem 5.9.13. [110, VI.14.4] If D is locally connected at u, a point of ∂D,
then u is accessible from D.

If u is an accessible point of ∂D and v a point of D, then there is an end-cut in D
joining u and v.If L u is an end-cut in D joining u and x,and L v asegment arc
joining x and v in D,let y be the first point of L u , counting from u, that lies in L v .
Then, the arc segments uy of L u and yv of L b together form the required end-cut.
Similarly, if u and v are accessible points of ∂D, there is a cross-cut uv in D.
We are now ready to prove Theorem 5.8.4.