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

If pred( x ) lies in the right component of N out ( y ) (see Fig. 6 ) then it must lie
in the segment of this circle cut off by the line through x and y , which implies
that

<d ʸ and so pred( x )= w . It follows that when the translation
is taken just to the point where w lies on the boundary of N out ( y ), at which
point y must still lie outside N out (pred( x )) (see Fig. 7 ), we have

pred( x ) x |

|

w y <d ʸ and

thus if we replace the edges w x and x y at this point by the edge w y , we must
have a path that satisfies the dcc-path property.
Similarly, if pred( x ) lies in the left half of N out ( y ) (see Fig. 6 ) then succ( y )
must lie in the left half of N in ( x ) and in fact in the segment of this circle cut
off by the line through x and y . As before, this implies that

| |

<d ʸ and
so succ( y )= z . It follows that when the translation is taken just to the point
where z lies on the boundary of N in ( x ), at which point x has not yet entered
the interior of N out ( y ) (see Fig. 7 ), we have

| succ( y ) y |

x z

<d ʸ and thus if we replace
the edges x y and yz at this point by the edge x z , we must have a path that
satisfies the dcc-path property.

| |

y

y

z

z

x

w x

w

x

x

w

w

Fig. 6. Fig. 7.

Since in both of these remaining cases the resulting path has one fewer edge
than P , the result follows. Note that the only situation where the path has not
had its length strictly reduced is where the inflection edges are parallel (and so
the translation is length preserving).

Remark 7. It is worth observing at this point that Lemma 3 applies as well to
the case in which the inflection edge xy is an endpoint inflection. In this case,
we are not able to conclude that the transformed path has one fewer edge (since
edge yz has length zero), but it does follow from our argument that if P cannot
be shortened then the endpoint inflection edge must be a chord of the circle that
defines the endpoint configuration at y .

It follows from Lemma 3 that, ignoring the length zero edges at the path end-
points, any discrete-geodesic is the concatenation of at most three inflection-free