On Polygonal Paths with Bounded Discrete-Curvature: The Inflection-Free Case - Discrete and Computational Geometry and Graphs - page 50

the fact that there are no known bounds on the minimum length or intricacy
(number of elementary segments), expressed as a function of the description of
the polygonal domain, of obstacle-avoiding paths in Dubins form. In a variety
of restricted domains polynomial-time algorithms exist that construct shortest
bounded-curvature paths [ 1 , 2 , 4 ].
A discretization of curvature-constrained motion was studied by Wilfong
[ 42 , 43 ]. However, his setting is different from ours since he considered discretized
environment , and not discrete paths. A practical way of producing paths with
length and turn constraints is presented in [ 41 ]. For some other recent work on
bounded-curvature paths see [ 3 , 5 , 11 , 16 , 17 , 21 , 22 , 24 ].

1.2 Our Approach

We study properties of discrete-geodesics that are free of inflections, as well as
their smooth counterparts. In Sect. 2 we motivate the study of this restricted class
of paths by proving that unrestricted discrete-geodesics never need more than
two internal inflections; i.e. all discrete geodesics are formed by the concatenation
of at most three inflection-free discrete-geodesics.
Section 3 establishes the central result of the paper: a precise characteriza-
tion of the form of all discrete-geodesics (if they exist). In Sect. 4 we use this
characterization to outline a proof of a characterization of smooth inflection-free
geodesics (establishing, by a simple limiting argument, this interesting variant
of the Dubins characterization). We also include a simple geometric proof of the
existence of one important special case of discrete-geodesics that illustrates the
strength of our characterization.
We note that similar methods, proving properties of smooth curves using
discretization, were already used by Schur in his paper of 1921; interestingly,
exactly these problems, considered by Schur [ 36 ] and Schmidt [ 35 ], led Dubins
to his result.

2 Inflections in Discrete-Geodesics

We now start our investigation of the structure of discrete-geodesics. An edge
e of a polygonal path is an inflection edge if the edges adjacent to e lie on the
opposite sides of (the supporting line of) e . Such an edge is said to have positive
inflection if the path makes a left turn into and a right turn out of e (and
negative inflection , otherwise). Note that, in accordance with our interpretation
of endpoint conditions as a zero-length edge of specified orientation, the first and
last edges of a path are possible inflection edges. When we want to distinguish
such edges, we refer to them as endpoint inflection edges ; other inflection edges
are referred to as internal inflection edges .
It is not hard to see that a dcc-path can have arbitrarily many inflection
edges (of arbitrary lengths). However, minimum length such paths, can have no
more than two internal inflection edges (of any length) in total .