5
$\begingroup$

I am given two metric spaces as two arrays of the same size. Each one is supposed to represent distance between vertices on a mesh in R^3. The meshes are assumed to have the same number of vertices and the correspondence betweeen the vertices is also given. Is there a way to find the a meaningful distance between these two matrices (other than the trivial ones)? I would like the distance be invariant under scaling : in other words if the first mesh's is just a scaling of the other mesh then I want the distance between the two corresponding metric spaces to be zero (even though the distances in the matrices have also been scaled).

I know that Hausdorff distance measures the distance between two sets in the same metric space but note here that my question is a little different so that notion is not exactly useful.

Thanks.

$\endgroup$
7
  • 1
    $\begingroup$ Do you also know the notion of Gromov-Hausdorff distance? Not exactly what you want, but close. Also I wonder about the close votes. $\endgroup$
    – Dirk
    Jan 10, 2017 at 20:13
  • 1
    $\begingroup$ If the correspondence is given, why can you not first normalize the first entry of both arrays to equal 1 to overcome the scaling problem? $\endgroup$ Jan 10, 2017 at 21:25
  • $\begingroup$ Also, you use the word array in some places and matrix in others. Am I correct in intuiting that what you have is some fixed number $N$ of labeled points and that the distances are encoded in an $N\times N$ matrix whose entries are the pairwise distances $d_{ij} = |v_i - v_j|$? // Also, what do you mean by "the trivial ones"? $\endgroup$ Jan 10, 2017 at 21:29
  • $\begingroup$ One of the votes to close is "unclear what you're asking". I think this question is perfectly reasonable, and perhaps some modification of GH distance is what is required $\endgroup$
    – Yemon Choi
    Jan 10, 2017 at 22:37
  • 1
    $\begingroup$ why not first normalize the two metrics, so that the sum of distances equals 1 (this is a slight modification of Willie Wong's suggestion) and then calculate some norm of the difference between the two lengths vectors, e.g. the euclidean length of that difference vector? $\endgroup$ Jan 11, 2017 at 9:25

2 Answers 2

3
$\begingroup$

Firstly, if you just have pairwise distances rather than coordinates of points in $\mathbb{R}^3$, then you can attempt to embed the mesh into $\mathbb{R}^3$ using Isomap. Under certain conditions, such as if you have a triangulated convex polyhedron, the isometric embedding into $\mathbb{R}^3$ is unique up to isometries of $\mathbb{R}^3$.

After you embed your meshes $X, Y$ as finite labelled subsets of $\mathbb{R}^3$, the problem of finding the optimal scaling and isometry which minimises the error $\sum_i \lVert X_i - Y_i \rVert_2^2$ is called Procrustes analysis. After applying this isometry, you get a canonical (root-mean-square) distance between the sets $X, Y$.

The way that Procrustes analysis usually proceeds is to subtract the mean, then scale to have unit variance, and then use singular value decomposition to find the optimal orthogonal matrix transforming $X$ to match $Y$ as closely as possible. The last part is called the Kabsch algorithm.

$\endgroup$
0
$\begingroup$

Persistent Homology can be used for this purpose. Given two metric spaces $X$ and $Y$, then one can measure the distance between their persistence diagrams $PD_i(X)$ and $PD_i(Y)$ where $i \geq 0$. There are many distances that can be defined on the space of persistence diagrams such as the bottleneck distance of the Wasserstein distance. The distance between the persistence diagram is much more efficient than the Hausdorff distance because usually the persistence diagram contains less data than the original spaces.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.