Information Technology Reference
In-Depth Information
Theorem 1.
If
ʳ
is any cc-path and
ʳ
any
ʸ
-discretization of
ʳ
, then (i)
ʳ
is a
ʸ
-bcc-path, and (ii)
sin(
ʸ/
2)
ʸ/
2
|
ʳ
|
≤|
ʳ
|≤|
ʳ
|
.
Proof.
(i) That
ʳ
is a
ʸ
-bcc-path is an immediate consequence of Corollary
2
,
since the angle between the ray
ʳ
(
t
i−
1
)
ʳ
(
t
i
)andtheray
ʳ
(
t
i
)
ʳ
(
t
i
+1
)isjustthe
sum of the angles formed by these rays with
ʳ
(
t
i
).
(ii) It is clear that the length of any
ʸ
-discretization of a smooth curve
ʳ
is no
greater than the length of
ʳ
. On the other hand, it follows immediately from
Corollary
1
that its length cannot be less than
sin(
ʸ/
2)
ʸ/
2
|
ʳ
|
.
The fact that the bounds on
coincide in the limit as
ʸ
approaches zero, will
be used to obtain properties of shortest smooth paths as a limit of the properties
of their discrete counterparts.
Remark 2.
It is worth noting at this point that our definition of
ʸ
-dcc-path,
because of its “local” nature, rules out some paths that may be seen as having
bounded curvature. For example, a “sawtooth” approximation of a straight line
(see Fig.
3
) does not qualify as a
ʸ
-dcc-path if the pitch of the teeth (turn angle),
no matter how small, is too sharp relative to the size of the teeth (edge length).
|
ʳ
|
Configurations.
A
configuration
is a pair (
p, ˆ
),
where
p
is a point and
ˆ
is a direction (unit
vector). We say that a polygonal path
P
=
1
satisfies endpoint configurations
(
v
1
,ˆ
1
) and (
v
n
,ˆ
n
) if (i) the difference between
the angle of the ray
v
1
v
2
and
ˆ
1
, is no more
than sin
−
1
(
min
{d
θ
,|v
1
v
2
|
2
), and (ii) the difference
between the angle of the ray
v
n−
1
v
n
and
ˆ
n
,isno
more than sin
−
1
(
min
{
d
θ
,
|
v
n−
1
v
n
|
2
).
Remark 3.
This is equivalent to asserting that the
path
v
1
,v
2
,...,v
n
ʸ
Fig. 3.
A sawtooth path that
does
not
qualify as a
ʸ
-dcc-
, formed from
P
by
adding an arbitrarily short edge of direction
ˆ
1
(respectively,
ˆ
n
) to the start (respectively, end)
of
P
, has bounded discrete-curvature.
v
0
,v
1
,v
2
,...,v
n
,v
n
+1
path.
Remark 4.
It is easy to confirm that, for
any
intermediate configuration (
v
i
,ˆ
i
),
the composition of any dcc-path
v
1
,v
2
,...,v
i
that satisfies endpoint config-
urations (
v
1
,ˆ
1
) and (
v
i
,ˆ
i
) with any dcc-path
v
i
,v
i
+1
,...,v
n
that satisfies
endpoint configurations (
v
i
,ˆ
i
) and (
v
n
,ˆ
n
) produces a dcc-path
v
1
,v
2
,...,v
n
that satisfies endpoint configurations (
v
1
,ˆ
1
) and (
v
n
,ˆ
n
). Furthermore, if
P
=
is any dcc-path that satisfies endpoint configurations (
v
1
,ˆ
1
)
and (
v
n
,ˆ
n
), then, for all
i
,1
<i<n
, there exists a direction
ˆ
i
such that (i)
the sub-path
v
1
,v
2
,...,v
n
is a dcc-path with endpoint configurations (
v
1
,ˆ
1
)
and (
v
i
,ˆ
i
), and (ii) the sub-path
v
1
,v
2
,...,v
i
is a dcc-path with endpoint
configurations (
v
i
,ˆ
i
) and (
v
n
,ˆ
n
). On the other hand, breaking
P
at an arbi-
trary point in the interior of one of its edges may produce a path that no longer
has bounded discrete-curvature (at the breakpoint).
v
i
,v
i
+1
,...,v
n
Search WWH ::
Custom Search