6
$\begingroup$

There are $n$ points in $R^2$ (i.e. the 2D real space). We can think of them as a complete graph where edge weights correspond to the distance between points.

Let $D$ be the distance matrix between all pairs of points, such that entry $D_{ij}$ corresponds to the distance between points $i$ and $j$. This matrix is of size $n \times n$ and the upper-triangle contains the distances between unique pairings of points.

Now imagine I put the elements from the upper triangle into a set, such that you no longer know which pairs of points produce the distance values. This is essentially the set of edge weights, with no information regarding the relationship between the weight and the edge the weight belongs to.

If you are given two sets and they are identical, does this imply the graphs corresponding to each set are also essentially the same?

Improve this question
$\endgroup$
5
  • $\begingroup$ What do you mean by same graph ? A graph can be translated and rotated to move some other position, yet the distances remains same. Are you considering these two graphs are same ? $\endgroup$
    – rnbguy
    Commented Jul 22, 2013 at 12:23
  • 2
    $\begingroup$ I think "Reconstructing Sets From Interpoint Distances" (cs.sunysb.edu/~skiena/papers/turnpike.ps‎ ) by Skiena, Smith, and Lemke answers the question (and the answer is no). $\endgroup$
    – Yota Otachi
    Commented Jul 22, 2013 at 13:57
  • $\begingroup$ This seems related to structural rigidity. A good follow up question would be asking what if the original $n$ points have algebraically independent coordinates. $\endgroup$
    – Chao Xu
    Commented Jul 23, 2013 at 3:51
  • $\begingroup$ @rnbcoder: yes, I am allowing translation and rotation, so 2 graphs (one translated/rotoated from the other) would be the same. $\endgroup$
    – RachM
    Commented Jul 31, 2013 at 5:42
  • $\begingroup$ @ChaoXu: yes, we can assume algebraically independent coordinates of the original n points. I read about rigidity, but it seems complete graphs are only rigid for a small n (I think it's for n <= 3, but I can't quite remember...). $\endgroup$
    – RachM
    Commented Jul 31, 2013 at 5:47

2 Answers 2

Reset to default
8
$\begingroup$

I think the following example with four points answers your question (though it gives multi-sets of distances). See Reconstructing Sets From Interpoint Distances by Skiena, Smith, and Lemke for more information.

example

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your example. I actually just came across the notion of "homometric" sets, which seems to answer my question (and the answer is "no"). Two sets are homometric if they are structurally different, and yet provide the same unordered pairwise distances. A nice toy example is the sets A = {0, 1, 2, 5, 7, 9, 12} and B = {0, 1, 5, 7, 8, 10, 12}. The (unordered) pairwise distances between elements in A is equal to the pairwise distance between elements in B, and yet A and B are quite different. Examples exist for points in 2D etc as well. $\endgroup$
    – RachM
    Commented Jul 31, 2013 at 5:45
  • $\begingroup$ I should also say I'm happy to have multisets of distances. $\endgroup$
    – RachM
    Commented Jul 31, 2013 at 5:52
0
$\begingroup$

A distance matrix uniquely characterizes a topology in a given space on some give elements given some property such as distance assuming a few ground hypotheses...

In your case, the distance matrix is defined from a given vertex to the other. If the matrix is symmetric with 0-diagonals, you have a simply connected graph. If you have diagonal elements, you are allowed to use self-loops and if the matrix is not symmetric, you have a digraph.

An analytic proof could go like this: assume the distance matrix did not characterize the graph uniquely, then you could build two graphs that are different from the same matrix...

Note that graph equivalence is usually defined in terms of isomorphism.

Additional information on the subject can be found in terms of spectral craph theory, which only defines isospectrality, not isomorphism.

Improve this answer
$\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.