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

Lemma 1. For any r and s , r<s<r + ˀ ,
in the domain of ʳ ,

y

2sin s−r
2

| ʳ ( s ) − ʳ ( r ) |≥ .

ʳ ( s )=( x ( s ) ,y ( s ))

Proof. Assume, without loss of generality,
that r = 0 and that ʳ ( r ) is at the origin O
(i.e. ʳ (0) = (0 , 0)); the lemma is then equiva-
lent to

ʷ =( y ( s ) , −x ( s ))

ʳ ( ˄ )

ʳ ( ˄ )

2sin 2 (Fig. 2 ). We prove this
by lower-bounding the derivative of

| ʳ ( s ) |≥

x

O

2 :

| ʳ ( s ) |

ʳ (0)

Fig. 2. |Oʳ ( s ) |≥ 2sin s
2

, the slope
of Oʳ ( s )isatmosttan s
2

.

( |ʳ ( s ) | 2 ) =2 ʳ ( s ) · ʳ ( s )=2 s
0

ʳ ( ˄ ) · ʳ ( s ) d˄ =2 s
0

≥ 2 s
0

cos ∠ s˄ d˄ cos( s − ˄ ) d˄ =2sin s

cos s )=4sin 2 2 . Hence | ʳ ( s ) |

2

≥ 2(1 −

sin( ʸ/ 2)
ʸ/ 2

Corollary 1. For al l i , 1 ≤ i<n , | ʳ ( t i +1 ) − ʳ ( t i ) |≥| t i +1 − t i | .

sin(( t i +1 − t i ) / 2)
( t i +1 −t i ) / 2

Proof. It suces to observe that, since 0 ≤ t i +1 − t i ≤ ʸ , ≥

sin( ʸ/ 2)
ʸ/ 2

.

Lemma 2. For any r and s , r<s<r + ˀ , in the domain of ʳ , the angle
between ʳ ( r ) and the ray ʳ ( r ) ʳ ( s ) is at most s−r
2

.

Proof. Assume again that r = 0 and that ʳ (0) = O ; also assume w.l.o.g.
that ʳ (0) is horizontal ( ʳ (0) = (1 , 0)). Let ʳ ( s )=( x ( s ) ,y ( s )), and let
k ( s )= y ( s ) /x ( s ) be the slope of the ray Oʳ ( s ) (Fig. 2 , left). Then the lemma is
equivalent to k ( s )

tan 2 , which we will prove by showing that k ≤

1 cos s

sin 2 s

−

≤ =

2cos 2 ( s/ 2) = (tan 2 ) .
By definition, for any ˄<s the angle between ʳ ( ˄ )and ʳ ( s ) is at most

1

˄ ; in particular ʳ ( s ) s . It follows that x ( s )=( x ( s ) ,y ( s )) (1 , 0) = ʳ ( s ) s − ≤ · ·

ʳ (0) = cos

∠ s 0 ≥ cos s , and thus x ( s ) ≥ sin s . Next, consider the unit vector

ʷ =( y ( s ) , x ( s )), orthogonal to ʳ ( s ) (Fig. 2 ). Since the angle between ʳ ( ˄ )

and ʷ is at least ˀ/ 2

−

˄ ), it follows that ( x ( ˄ ) ,y ( ˄ ))

− ( s − · ʷ ≤ cos( ˀ/ 2 − ( s − ˄ )),

or x ( ˄ ) y ( s ) y ( ˄ ) x ( s ) − ≤ sin( s − ˄ ). Integrating over ˄ from0to s ,weget

x ( s ) y ( s ) y ( s ) x ( s ) − ≤ 1 − cos s . Combining this with x ( s ) ≥ sin s , we obtain

what we need: k =( y/x ) = y x − x y
x 2

1 − cos s

sin 2 s

≤

.

Corollary 2. The angle between the ray ʳ ( t i− 1 ) ʳ ( t i ) and ʳ ( t i ) is at most sin − 1
( min { d θ , | ʳ ( t i− 1 ) ʳ ( t i ) |}
2

)

Proof. By the lemma, the angle between the ray ʳ ( t i− 1 ) ʳ ( t i )and ʳ ( t i )isatmost
t i − t i− 2 , which is always at most ʸ/ 2=sin − 1 ( d 2 ). So, it suces to consider the
case where

t i −t i− 1
2

sin − 1 ( |ʳ ( t i− 1 ) ʳ ( t i ) |
2

| ʳ ( t i− 1 ) ʳ ( t i ) | <d ʸ . But in this case, ≤ ),

by Lemma 1 .

In summary, we have shown the following: