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

c c c

a b

d

a b

d

a b

d

q q

p p

z z z

y y

r r

y

s s

w

w w

x x x

Fig. 14. Fig. 15. Fig. 16.

the second of these holds. Then, if we break edge xy at point r and translate
the second arc, including the point r , along the first bridge edge, the point r
must encounter the circle associated with the third arc before p reaches b .Ifwe
stop the translation at this point (see Fig. 16 ) we see that the second bridge has
been replaced by two edges ( xr and ry ) which become part of the second and
third discrete arc respectively; i.e. vertex r is a degenerate bridge, taking us to
Case II. (As before, we note that the translation produces a path that violates
the discrete bounded curvature property initially, but it is restored just when s
coincides with r .)

Case II: one bridge is degenerate and the other is not. We assume, without loss
of generality, that the first bridge is degenerate. There are two sub-cases again
that depend on the span of the second arc. In the first sub-case (see Fig. 17 )the
total turn from the first edge ( bc ) after the degenerate bridge ( b ) to the second
bridge edge ( xy )islessthanorequalto ˀ . If we translate the middle discrete arc,
excluding the first bridge point, (i.e. the vertices c through x ) along the second
bridge edge (taking x towards y ) (see Fig. 18 ), we maintain the discrete bounded
curvature property until the first of two events occurs: (i) x (respectively, y ) joins
the third (respectively, second) circle, or (ii) the successor ( c ) of the degenerate
bridge ( b ) joins the first circle. The first event coincides with the degeneration of
the second bridge, while the second event leaves us with a new degenerate first
bridge (vertex c ), and hence a new instance of Case II with a smaller second arc.
In the second sub-case (see Figs. 19 and 21 ), where the total turn from the
first edge ( bc ) after the degenerate bridge ( b ) to the second bridge edge ( xy )is
greater than ˀ , we again slide the middle discrete arc, this time including the
first bridge point, (i.e. the vertices b through x ) along the second bridge edge
(taking x towards y ). The discrete bounded curvature property is maintained at
x and y unless x (respectively, y ) joins the third (respectively, second) circle (i.e.
the second bridge becomes degenerate). Meanwhile, if b moves outside of the first
circle (see Fig. 20 ), then the discrete bounded curvature property is maintained
at a and b until a joins the second circle, at which point a replaces b as a
degenerate bridge, so we can continue in Case II. Alternatively, if b moves inside
the first circle, we maintain feasibility of the transformed path by (continuously)