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

On Polygonal Paths with Bounded
Discrete-Curvature: The Inflection-Free Case

B

Sylvester Eriksson-Bique 1 , David Kirkpatrick 2(

) , and Valentin Polishchuk 3

1 Courant Institute, New York, USA
[e-mail]
2 University of British Columbia, Vancouver, Canada
[e-mail]
3 University of Helsinki, Helsinki, Finland
[e-mail]

Abstract. A shortest path joining two specified endpoint configurations
that is constrained to have mean curvature at most

˂

on every non-zero

length sub-path is called a . A seminal result in non-holonomic

motion planning is that (in the absence of obstacles) a 1-geodesic consists
of either (i) a (unit-radius) circular arc followed by a straight segment
followed by another circular arc, or (ii) a sequence of three circular arcs
the second of which has length at least ˀ [Dubins, 1957]. Dubins' original
proof uses advanced calculus; Dubins' result was subsequently rederived
using control theory techniques [Sussmann and Tang, 1991], [Boissonnat,
Cerezo, and Leblond, 1994], and generalized to include reversals [Reeds
and Shepp, 1990].
We introduce and study a discrete analogue of curvature-constrained
motion. Our overall goal is to show that shortest polygonal paths of
bounded “discrete-curvature” have the same structure as ˂ -geodesics,
and to show that properties of ˂ -geodesics follow from their discrete
analogues as a limiting case, thereby providing a new, and arguably sim-
pler, “discrete” proof of the Dubins characterization. Our focus, in this
paper, is on paths that have non-negative mean curvature everywhere; in
other words, paths that are free of inflections, points where the curvature
changes sign. Such paths are interesting in their own right (for example,
they include an additional form, not part of Dubins' characterization),
but they also provide a slightly simpler context to introduce all of the
tools that will be needed to address the general case in which inflections
are permitted.

˂-geodesic

1 Introduction

Curvature-constrained paths are a fundamental tool in planning motion with
bounded turning radius. Paths that are smooth (continuously differentiable) have
the advantage that they may look more appealing and realistic than polygonal
(piecewise-linear) paths. Nevertheless, polygonal paths are a much more common
model in geometry, exactly because of their discrete nature, and for this same
reason they have the potential of providing simpler and more intuitive proofs
c