8
$\begingroup$

Suppose we have a collection of exactly $N$ points (say $N=1000$), with each point belonging to 2-dimensional Euclidean space $\mathbb{R}^2$, but we don't know the coordinates of the points. Suppose that we instead have, for some pairs of points, an approximation for the Euclidean distance between them.

Question: How can we find an approximation of the coordinates of these points (up to flip/rotations of the plane) in the plane?

I.e., we want to embed the points in the plane in a way that is as consistent as possible with the estimated distances. (Note: These distances might turn out to be inconsistent, since they're approximations.)

I need something that I can actually implement on a computer.

Motivation: This question arises from studying geometric graphs in the plane: we can approximate the Euclidean distance between vertices by studying the number of common neighbours. More common neighbours imply the vertices are more likely to be closer together. But not all pairs of vertices have common neighbours, in which case we don't have an estimate.

$\endgroup$
2
  • 1
    $\begingroup$ Not quite what you are looking for, but it's worth pointing out there is a large literature on graph rigidity. If you know the distances exactly and the graph is 6-connected then you can in principle calculate the locations up to symmetry. See eg arxiv.org/abs/1201.3727 and references therein. $\endgroup$
    – user25199
    Sep 18, 2013 at 22:29
  • $\begingroup$ Following up Carl's comment, an embedding of a graph is determined (up to isometries) by the lengths of its edges if the graph is "globally rigid". So if you're interested in knowing whether a given set of estimates of vertex pair distances (edges) is sufficient for your vertex set, you might check out this related question and its answers mathoverflow.net/questions/63510/… $\endgroup$
    – j.c.
    Sep 18, 2013 at 23:00

2 Answers 2

7
$\begingroup$

One standard thing is to simulate a network of springs, one per data that you have, such that each spring wants to have the length corresponding to your estimate. In other words, if $l_{ij}$ is your estimate, you can look at the energy $$H((x_i)) = \sum [l_{ij} - \|x_j-x_i\|]^2$$ or something similar. Of course the sum runs over all pairs for which you have an estimate. Then minimize H, which can be done numerically in a reasonably efficient way because of the shape of $H$.

Software packages like graphviz do that, and so does Mathematica IIRC.

$\endgroup$
2
  • $\begingroup$ Can you give some hints which part of graphviz does this? $\endgroup$
    – math
    Nov 7, 2013 at 9:40
  • $\begingroup$ I believe fdp and sfdp implement something like that, where by default $l_{ij}=1$ but you can specify a length for an edge to set another value. $\endgroup$ Nov 7, 2013 at 14:13
6
$\begingroup$

For complete distance information, this is known as "multidimensional scaling" and heavily used in social sciences or psychology. Actually, there is a very simple approach in this case based on the singular value decomposition and this goes back to Householder and Young in the paper "Discussion of a set of points in terms of their mutual distances".

In the case of limited data, one can approach this via matrix completion, i.e. try to find a full distance matrix, i.e. a matrix $D$, such that $D_{i,j} = \|x_i-x_j\|$ for some points $x_i$ which has the known entries (up to an error) in the right places. See, e.g. "Solving Euclidean Distance Matrix Completion Problems Via Semidefinite Programming" by Alfakih, Khandani and Wolkowicz or "Low-rank optimization for distance matrix completion" by Mishra, Meyer and Sepulchre.

$\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.