NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
A Fast Algorithm for Elastic Shape Distances Between Closed Planar Curves
Published
Author(s)
Gunay Dogan, Javier Bernal, Robert C. Hagwood
Abstract
Effective computational tools for shape analysis are needed in many areas of science and engineering. We address this and propose a fast algorithm to compute the geodesic distance between elastic closed curves in the plane. The original algorithm for the distance has cubic time complexity with respect to the number of nodes on the curve. Hence, it is not suitable for large shape data sets. We aim for large-scale shape analysis and thus propose a novel iterative algorithm with quadratic time complexity. In practice, we observe subquadratic, almost linear, running times, and that our algorithm scales very well with large numbers of nodes on the curves. The key to our algorithm is the decoupling of the optimization for the starting point and rotation and the optimization for the reparameterization function. Moreover, we develop a fast dynamic programming algorithm and a nonlinear constrained optimization algorithm that work in tandem to compute optimal reparameterizations fast.
Proceedings Title
IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2015
Dogan, G.
, Bernal, J.
and Hagwood, R.
(2015),
A Fast Algorithm for Elastic Shape Distances Between Closed Planar Curves, IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2015, Boston, MA, [online], https://doi.org/10.1109/CVPR.2015.7299050
(Accessed October 9, 2025)