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

d

y

y

b c

c

z

e

x

d

b

a

a

Fig. 29. Fig. 30.

the corresponding endpoint configuration and (ii) cuts the middle circle with a
maximal chord.
Taking this into consideration, Theorem 2 can be strengthened to provide
a very tight characterization of the form of inflection-free ʸ -discrete-geodesics,
if they exist: they are formed by two (or fewer) ʸ -discrete circular arcs of the
same orientation, joined by a (possibly degenerate) bridge, and preceded and
followed by (possibly degenerate) edges that are extensions of the endpoint con-
figurations. Furthermore, when the extension of one endpoint configuration is
non-degenerate, either (i) there is only a single non-degenerate ʸ -discrete circular
arc, or (ii) the extension of the other endpoint configuration must be degenerate,
and the adjacent ʸ -discrete circular arc must span more than a half circle.
We note that, as ʸ goes to zero, this refined characterization of inflection-
free ʸ -discrete-geodesics describes a family of smooth geodesics, including the
sole inflection-free geodesic specified by Dubins' general characterization. In this
way, we can derive an analogue of Dubins' result for inflection-free geodesics.
Uniqueness, in the smooth case, is a direct consequence of the uniqueness of their
discrete counterparts, together with our discretization theorem (Theorem 1 ).
Clearly paths of the form specified by Theorem 2 , joining specified end-
point configurations, always exist. To argue the existence of discrete-geodesics,
it remains to argue that the infimum of the lengths of paths of this form is
always realized by a path of this form. It would suce to use a compactness
argument (of the style used by Dubins), but it turns out to be both simpler and
more revealing to argue this geometrically. We will do so for general (not nec-
essarily inflection-free) discrete-geodesics in a companion paper. To give some
sense of the kind of arguments involved, we consider just one special case here:
an inflection-free dcc-path is endpoint-anchored if it is formed by two ʸ -discrete
circular arcs respecting the two endpoint constraints, joined by a bridge of length
at least 2 d ʸ . (Note that such paths correspond to the unique inflection-free paths
in Dubin's characterization, in the limit as ʸ goes to zero.)
To this end, we say that a ʸ -discrete arc consisting of a sequence of edges
of length exactly d ʸ is perfect , and a ʸ -discrete arc consisting of a sequence of
edges all but one of which have length exactly d ʸ is near-perfect . With this, we
can assert that:

Claim 3. Endpoint-anchored geodesics exist and are composed of two perfect
discrete circular arcs joined by a non-degenerate bridge.