  We propose the first algorithm for non-rigid 2D-to-3D shape matching, where
the input is a 2D shape represented as a planar curve and a 3D shape
represented as a surface; the output is a continuous curve on the surface. We
cast the problem as finding the shortest circular path on the product
3-manifold of the surface and the curve. We prove that the optimal matching can
be computed in polynomial time with a (worst-case) complexity of
$O(mn^2\log(n))$, where $m$ and $n$ denote the number of vertices on the
template curve and the 3D shape respectively. We also demonstrate that in
practice the runtime is essentially linear in $m\!\cdot\! n$ making it an
efficient method for shape analysis and shape retrieval. Quantitative
evaluation confirms that the method provides excellent results for sketch-based
deformable 3D shape retrieval.
