A polynomial-time relaxation of the Gromov-Hausdorff distance
This provides a practical solution for researchers in computational geometry and data analysis dealing with shape matching and point-cloud comparison, though it is incremental as it relaxes an existing metric.
The paper tackles the computational intractability of the Gromov-Hausdorff distance by introducing a polynomial-time semidefinite programming relaxation, which is shown to be a pseudometric and applied to shape matching and point-cloud comparison with algorithms handling hundreds of points.
The Gromov-Hausdorff distance provides a metric on the set of isometry classes of compact metric spaces. Unfortunately, computing this metric directly is believed to be computationally intractable. Motivated by applications in shape matching and point-cloud comparison, we study a semidefinite programming relaxation of the Gromov-Hausdorff metric. This relaxation can be computed in polynomial time, and somewhat surprisingly is itself a pseudometric. We describe the induced topology on the set of compact metric spaces. Finally, we demonstrate the numerical performance of various algorithms for computing the relaxed distance and apply these algorithms to several relevant data sets. In particular we propose a greedy algorithm for finding the best correspondence between finite metric spaces that can handle hundreds of points.