Hardness Results for Two-Dimensional Curvature-Constrained Motion Planning
David G. Kirkpatrick, Irina Kostitsyna, Valentin Polishchuk · 2011
We revisit the problem of finding curvature-constrained paths in a polygonal domain with holes. We give a new proof that finding a shortest curvature-constrained path is NP-hard; our proof is substantially simpler, and makes fewer assumptions about the polygonal domain, than the earlier proof of [Reif and Wang, 1998]. We also prove that it is NP-hard to decide existence of a simple (i.e., non-self-intersecting) path. 1