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

2.1 More than Two Internal Inflection Edges is Impossible

Our first observation is that in any discrete-geodesic there can be at most one
internal inflection edge of each turn type.

Lemma 3. Any ʸ -dcc-path containing two or more internal inflection edges of
the same type can be replaced by another ʸ -dcc-path, with fewer edges, whose
total length is no longer than the original. In fact, if the inflection edges are
non-parallel, the replacement path is strictly shorter.

Proof. Let P = and suppose that both bc

and xy are internal inflection edges with positive inflection (i.e. P turns left at
both b and x and right at both c and y ; see Fig. 4 ). Note that since edges bc
and xy are internal inflection edges, the edges ab , cd , wx and yz all have strictly
positive length.

v 1 ,...,a,b,c,d,...,w,x,y,z,...,v n

N in ( x )

N out ( y )

N in ( x )

v 1

y
x

z

w

c

x

a

d

w

w

b

y

x

v n

z

Fig. 4. A is r te r t r -
constrained path with two positive
inflection edges

Fig. 5. Full translation

bc and xy .

We assume, without loss of generality, that the ray from b through c and the
ray from x through y are either parallel or diverge (as illustrated). Then, any
transformation of P that results from a translation of the sub-path between c
and x along the vector xy (taking c,...x to c ,...x ) reduces the length of P
(except when the inflection edges are parallel, in which case the length of P is
preserved) and maintains the dcc-path property at b and c (since the edge bc
lengthens, while the turns at both b and c are not increased).
Consider the situation when x has been translated all the way to y (see
Fig. 5 ). The dcc-path property holds for the resulting path as long as pred( x )
lies in N out ( y ) (or, equivalently, succ( y ) lies in N in ( x )), where x denotes the
translation of x , etc. In this case, there is nothing left to prove since the path
has one fewer edge (namely xy ) than P . Hence we can assume that, after this
full translation, pred( x ) lies in N out ( y ).