liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
On Polygonal Paths with Bounded Discrete-Curvature: The Inflection-Free Case
Courant Institute, New York, USA .
University of British Columbia, Vancouver, Canada .
University of Helsinki, Helsinki, Finland .
2014 (English)In: Discrete and Computational Geometry and Graphs: 16th Japanese Conference, JCDCGG 2013, Tokyo, Japan, September 17-19, 2013, Revised Selected Papers / [ed] Jin Akiyama, Hiro Ito, Toshinori Sakai, Springer International Publishing , 2014, 44-64 p.Chapter in book (Other academic)Text
Abstract [en]

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 ς'>ς ς-geodesic. A seminal result in non-holonomic motion planning is that (in the absence of obstacles) a 1'>1 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, Cérézo, 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 simpler, “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.

Place, publisher, year, edition, pages
Springer International Publishing , 2014. 44-64 p.
National Category
Computer Science
URN: urn:nbn:se:liu:diva-128025DOI: 10.1007/978-3-319-13287-7_5ISBN: 978-3-319-13287-7ISBN: 978-3-319-13286-0OAI: diva2:928734
Available from: 2016-05-16 Created: 2016-05-16 Last updated: 2016-05-25

Open Access in DiVA

No full text

Other links

Publisher's full textfind book at a swedish library/hitta boken i ett svenskt bibliotek
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 3 hits
ReferencesLink to record
Permanent link

Direct link