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

of properties of their smooth counterparts. Furthermore, from an applications
perspective, polygonal paths are more natural to plan, describe and follow. For
instance, in air trac management—one of our motivating applications—an air-
craft flight plan (a list of “waypoints”) is represented on the strategic level by
a polygonal path whose vertices are the GPS waypoints. The actual smoothly
turning trajectory at a waypoint is decided by the pilot on the tactical level
when executing the turn (see [ 25 ] for more on curvature-constrained route plan-
ning in air transport). We are thus motivated to formulate a discretized model
of curvature-constrained motion.

Smooth paths of bounded curvature. In studying smooth paths of bounded cur-
vature, L. E. Dubins [ 15 ] observed that if one restricts attention to paths whose
curvature is defined at every point then there are situations in which short-
est paths do not exist. On the other hand, if one only requires that paths are
everywhere differentiable (that is their slope is well-defined at every point) then
their mean curvature is well-defined on every non-zero length sub-path. Thus,
Dubins chose to define a path to have bounded curvature if its mean curvature
is bounded everywhere. Specifically, let ʳ be a smooth path, parameterized by
its arclength. For any t in the domain of ʳ ,let ʳ ( t ) denote the derivative of
ʳ at t - the unit vector tangent to ʳ at t . The path ʳ is said to have mean
curvature at most one if

st denotes
the angle between the directions of ʳ ( s )and ʳ ( t ). (In other words, ʳ ,viewed
as mapping from the domain of ʳ to the unit circle, is 1-Lipschitz.) Furthermore,
there is no loss of generality in restricting attention to the case where the mean
curvature bound is one, since the general case can be reduced to the unit case by
suitable scaling. Accordingly, we hereafter use the term “curvature-constrained”
as a shorthand for “has mean curvature bounded by one”, and we refer to paths
with this property as cc-paths .
Dubins' characterization, a seminal result in curvature-constrained motion
planning, states that, in the absence of obstacles, shortest curvature-constrained
paths in the plane, are one of two types: (i) a circular arc followed by a line
segment followed by another arc, or (ii) a sequence of three circular arcs, the
second of which has length at least ˀ .

∠ st ≤ s − t , for any t<s<t + ˀ , where ∠

Discrete circular arcs. While several possibilities suggest themselves as ways
to formulate a discrete analogue of unit-bounded curvature 1 , it seems that all
such formulations are based on a natural notion of discrete circular arcs. Let
0 <ʸ

ˀ/ 2 be a given angle. We say that a polygonal chain forms a ʸ -discrete
circular arc (or simply a discrete circular arc if ʸ is understood) if (i) its vertices
belong, in sequence, to a common circle of radius one, and (ii) successive edges
have length at most d ʸ =2sin 2 (that is they subtend a circular arc of length
at most ʸ ). Any portion of regular polygon with k

≤

≥

3 sides, inscribed in a unit
circle, provides a prototypical (2 ˀ/k )-discrete circular arc.

1 In an earlier draft [ 18 ], the authors proposed an alternative definition which had
some deficiencies that are resolved by the definition used in this paper.