Information Technology Reference
In-Depth Information
Proof. The key to establishing the existence of discrete-geodesics is the observa-
tion that any minimum length discrete arc spanning an angle ʨ is made up of
segments of length d ʸ , and one additional edge spanning an arc of length
ʨ mod ʸ , i.e. it is near-perfect.
Suppose we have a dcc-path that consists of a near-perfect, but non-perfect,
discrete arc followed by a non-degenerate bridge, followed by another near-
perfect discrete circular arc. It remains to argue that such a path is not a
discrete-geodesic, i.e. it can be shortened. There are two cases to consider. The
first, shown in Fig. 29 , the chord bd of length d ʸ from b , the last vertex on the
initial perfect arc, crosses the bridge cy . In this case, it is straightforward to
show (since
ʨ/ʸ
) that replacing sub-path
bcy by bdy must produce a shorter dcc-path with the same endpoints.
Alternatively, we can assume (see Fig. 30 ) that neither bd nor the correspond-
ing chord xz on the second circle cross the bridge cy . In this case, if we pivot the
bridge cy about its endpoint y then the dcc-path property is preserved until the
bridge hits the first of b , d or x . But since this transformation leads to a shorter
path in all three situations.
|
bd
|
+
|
de
|≤|
bc
|
+
|
ce
|
and
|
dy
|
<
|
de
|
+
|
ey
|
5 Conclusion
We introduced a discrete model of curvature-constrained motion and studied
some of its properties, in particular the structure of geodesics in this model. Our
focus here has been primarily on inflection-free paths, which we have demon-
strated constitute an essential component of unrestricted geodesics. We have
also illustrated the utility of our characterization in relating properties of smooth
geodesics as the limiting case of our discrete geodesics.
In a subsequent paper we will extend our characterization of inflection-
free discrete-geodesics to the general case, including a re-derivation of the full
Dubins characterization of smooth geodesics, using similar limiting arguments.
We believe that discrete versions of curvature-constrained motions that include
reversals (cf. [ 31 ]) can be formulated in the same way.
Acknowledgements. We thank Sergey Bereg, Stefan Foldes, Irina Kostitsyna and
Joe Mitchell for discussions.
References
1. Agarwal, P.K., Biedl, T., Lazard, S., Robbins, S., Suri, S., Whitesides, S.:
Curvature-constrained shortest paths in a convex polygon. In: SoCG (1998)
2. Agarwal, P.K., Raghavan, P., Tamaki, H.: Motion planning for a steering-
constrained robot through moderate obstacles. In: SToC, pp. 343-352 (1995)
3. Ahn, H.-K., Cheong, O., Matousek, J., Vigneron, A.: Reachability by paths of
bounded curvature in a convex polygon. Comput. Geom. 45 (1-2), 21-32 (2012)
4. Bereg, S., Kirkpatrick, D.: Curvature-bounded traversals of narrow corridors.In:
SoCG, pp. 278-287 (2005)
Search WWH ::




Custom Search