Problem 43007. Euclidean inter-point distance matrix

Created by John D'Errico

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Euclidean distance between two points in a p-dimensional space is a really common thing to compute in the field of computational geometry. In fact, it is pretty easy to do. norm(u-v) would seem to do the trick, for vectors u and v.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>But what if you have a large number of points between which you want to compute ALL of those distances between every pair of points? In this problem, given an n by p array A, where each row of the matrix will be viewed as containing the coordinates of one p-dimensional point, you need to compute the n by n inter-point distance matrix.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Thus, D(i,J) will be the Euclidean distance between the i'th and j'th rows of A. Of course, D will be a symmetric matrix, with zeros on the diagonal.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>So you can test your code, here is an example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[A = [1 1\n 5 2\n 2 2\n 4 5]\n\nformat short g\nD = interDist(A)\nD =\n 0 4.1231 1.4142 5\n 4.1231 0 3 3.1623\n 1.4142 3 0 3.6056\n 5 3.1623 3.6056 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Thus, thinking of the points [1 1] and [5 2] as the coordinates of two points in the (x,y) plane, the Euclidean distance between them in that plane is 4.1231...</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>As you can see, the matrix is symmetric, with zeros on the main diagonal. That must always happen, since the distance between any point and itself must be zero.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

The Euclidean distance between two points in a p-dimensional space is a really common thing to compute in the field of computational geometry. In fact, it is pretty easy to do. norm(u-v) would seem to do the trick, for vectors u and v.But what if you have a large number of points between which you want to compute ALL of those distances between every pair of points? In this problem, given an n by p array A, where each row of the matrix will be viewed as containing the coordinates of one p-dimensional point, you need to compute the n by n inter-point distance matrix.Thus, D(i,J) will be the Euclidean distance between the i'th and j'th rows of A. Of course, D will be a symmetric matrix, with zeros on the diagonal.So you can test your code, here is an example:<pre class="language-matlab">A = [1 1
 5 2
 2 2
 4 5]
</pre><pre class="language-matlab">format short g
D = interDist(A)
D =
 0 4.1231 1.4142 5
 4.1231 0 3 3.1623
 1.4142 3 0 3.6056
 5 3.1623 3.6056 0
</pre>Thus, thinking of the points [1 1] and [5 2] as the coordinates of two points in the (x,y) plane, the Euclidean distance between them in that plane is 4.1231...As you can see, the matrix is symmetric, with zeros on the main diagonal. That must always happen, since the distance between any point and itself must be zero.

The Euclidean distance between two points in a p-dimensional space is a really common thing to compute in the field of computational geometry. In fact, it is pretty easy to do. norm(u-v) would seem to do the trick, for vectors u and v.

But what if you have a large number of points between which you want to compute ALL of those distances between every pair of points? In this problem, given an n by p array A, where each row of the matrix will be viewed as containing the coordinates of one p-dimensional point, you need to compute the n by n inter-point distance matrix.

Thus, D(i,J) will be the Euclidean distance between the i'th and j'th rows of A. Of course, D will be a symmetric matrix, with zeros on the diagonal.

So you can test your code, here is an example:

A = [1 1
       5 2
       2 2
       4 5]

format short g
  D = interDist(A)
  D =
         0       4.1231       1.4142            5
    4.1231            0            3       3.1623
    1.4142            3            0       3.6056
         5       3.1623       3.6056            0

Thus, thinking of the points [1 1] and [5 2] as the coordinates of two points in the (x,y) plane, the Euclidean distance between them in that plane is 4.1231...

As you can see, the matrix is symmetric, with zeros on the main diagonal. That must always happen, since the distance between any point and itself must be zero.

Solve

Solution Stats

30 Solutions
19 Solvers

Last Solution submitted on Dec 30, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 1033317

1 Comment

1 Comment

Alfonso Nieto-Castanon on 27 Oct 2016

implicit expansion = strange-looking matrix algebra

Solution 989507

1 Comment

1 Comment

John D'Errico on 2 Oct 2016

nice

Problem Recent Solvers19

Problem Tags

computational geometry distance euclidean numerical methods

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!