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

fact that the slope of edge qc must exceed the slope of edge xs .) Without loss
of generality, we assume that the first of these holds. Then, if we break edge
bc at point p and translate the second arc along the second bridge edge, the
second circle (specifically point q ) must meet point p before x reaches r (note
that, since

= d ʸ , x reaches r before y enters the second circle). If we stop
the translation at this point (see Fig. 13 ) we see that the first bridge has been
replaced by two edges ( bp and pc ) which become part of the first and second
discrete arc respectively; i.e. vertex p is a degenerate bridge, taking us to Case
II. (It is worth noting here that as the translation takes q to p the discrete
bounded curvature property is initially violated at c . It is restored just when
q coincides with p . This is the reason why we need to ensure that the bridge
remains feasible for vertices x and y until q reaches p . It is not at all clear that
a transformation exists that is guaranteed to shorten the path in the situation
under consideration, while preserving the discrete bounded curvature property
throughout.)
The second sub-case, where the turn from the first bridge edge to the
second is greater than ˀ (see Fig. 14 ), is treated in a very similar fashion.
As in the first sub-case, we note that if we slide the middle discrete arc
along the first bridge edge (taking c towards b ) we maintain the discrete
bounded curvature property at b and c as long as b (respectively, c ) lies outside
the second (respectively, first) circle (i.e. until the first bridge becomes degener-
ate). Meanwhile the discrete bounded curvature property is maintained at the
endpoints of the second bridge edge ( xy ) as long as the successor ( r ) of the inner
point ( x ) lies outside of the second circle (because of the direction of the trans-
lation the predecessor of the other bridge endpoint ( y ) cannot enter the third
circle). If this point r meets the second circle (a maximal chord event) while
outside of the third circle, then point r can replace x as the inner point of the
second bridge (leading to a lengthening of the second discrete arc), and we can
continue in Case I.
By symmetry the analogous properties hold if we slide the middle discrete
arc along the second bridge edge (taking x to y ). Since both of these translations
serve to shorten the curve, we can assume that they have been done until either
or both of the bridges have degenerated (taking us to Case II or Case III below)
or we are left with unresolved maximal chord events on both bridges. In the
latter case, the predecessor point of c (illustrated by p in Fig. 15 ) must lie on the
first circle, the successor point of x (illustrated as r ) must lie on the third circle,
and p (respectively, r ) must lie inside the first (respectively, second) circle.
To deal with this last situation, we observe that either (i) the distance

| ry |

|
must be at least the distance from p to the point q on the circle associated with
the first arc intersected by the line through p with the slope of the second bridge
edge, or (ii) the distance

| ry

must be at least the distance from r to the point
s on the circle associated with the third arc intersected by the line through r
with the slope of the first bridge edge. (As before, it is easily confirmed that if
neither of these hold, we get a contradiction of the fact that the slope of edge
bq must exceed the slope of edge ys .) Assume, without loss of generality that

| pb |