Given the discussion from:

Representability of finite metric spaces

it appears that a 1974 paper by Morgan gives the criteria for when a distance metric can be embedded in Euclidean space. My first question is, what are some examples of metrics that satisfy his criteria? Some popular metrics that immediately come to mind are:

Levenstein distance (https://en.wikipedia.org/wiki/Levenshtein_distance)

Jaccard distance (https://en.wikipedia.org/wiki/Jaccard_index)

Can they be represented in R^n?

My second question is, if a metric does meet the criteria, how do we place the points in Euclidean space?

Thirdly, Morgan's result seems really profound. Why is it hardly cited? Is there an equivalent set of criteria that is more widely known?

Thank you!

  • 2
    $\begingroup$ In my opinion the first two questions of yours can be answered by going through the answers in the question linked to by you (using Schoenberg's theorem, using multidimensional scaling, looking at problems on EDMs etc.). $\endgroup$ – Suvrit Oct 8 '15 at 18:35
  • $\begingroup$ I would like to know some examples of popular metrics that can/cannot be represented in Euclidean space based on Morgan's criteria, or Schoenberg's theorem. $\endgroup$ – McFourier Oct 8 '15 at 18:47
  • $\begingroup$ perhaps we should look for metrics non-embeddable in $\mathbb{R^n}$ like perhaps let $d=d_1d_2...d_n, e=e_1...e_n$, $|d-e|=d_1e_2+...+d_ne_1$ $\endgroup$ – JMP Oct 9 '15 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.