Agarwal, Pankaj K.; Biedl, Therese; Lazard, Sylvain; Robbins, Steve; Suri, Subhash; Whitesides, Sue Curvature-constrained shortest paths in a convex polygon. (English) Zbl 1008.68143 SIAM J. Comput. 31, No. 6, 1814-1851 (2002). Summary: Let \(B\) be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let \(\mathcal P\) be a convex polygon with \(n\) vertices. We study the collision-free, optimal path-planning problem for \(B\) moving between two configurations inside \(\mathcal P\). (A configuration specifies both a location and a direction of travel.) We present an \(O(n^{2} \log n)\) time algorithm for determining whether a collision-free path exists for \(B\) between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvature-constrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. For example, we prove that any such shortest path is comprised of at most eight segments, each of which is a circular arc of unit radius or a straight-line segment. Some of the properties are quite general and shed some light on curvature-constrained shortest paths amid obstacles. Cited in 7 Documents MSC: 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) Keywords:nonholonomic motion planning; shortest paths; mobile robot; curvature constraint; bounded radius of curvature; Dubins path; computational geometry PDFBibTeX XMLCite \textit{P. K. Agarwal} et al., SIAM J. Comput. 31, No. 6, 1814--1851 (2002; Zbl 1008.68143) Full Text: DOI