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

w

w

w

y

w

z

z

x

x

x = y

x

Fig. 8. Fig. 9.

sub-paths. This motivates our next focus on the form of inflection-free discrete-
geodesics.

3 A Normal Form for Inflection-Free Geodesics

We have already noted that any short-
est dcc-path of minimum size consists
of a finite number of maximal dis-
crete circular arcs connected by (pos-
sibly degenerate) line segments that
we refer to as bridges . Here we include
the (possibly degenerate) circular arcs
(e.g. vertex k in Fig. 10 ) supported
by the circles (shown as dashed) that
define the endpoint configurations of
the path. A bridge vw is degenerate if
v = w (e.g. the first bridge, vertex d ,
in Fig. 10 ). Of course, if a given path
has no inflection edges, all of the dis-
crete circular arcs have the same ori-
entation; without loss of generality we will assume that they are all clockwise
oriented (see Fig. 10 ).
The main result of this section is the following theorem. It amounts to a
special case of a general characterization theorem for discrete-geodesics and is a
fundamental building block for the proof of that theorem.

f

g

e

d

h

c

i

b

j

k

a

Fig. 10. A discrete-curvature-constrained
path with five discrete arcs (including one
degenerate arc) and no inflections.

Theorem 2. Any inflection-free discrete-geodesic, joining two specified end-
point configurations, is composed of a sequence of at most four discrete circular
arcs, at most two of which are non-degenerate, joined by (possibly degenerate)
bridges.