Finding the coordinates of points from distance matrix

by

The answers based on angles are cumbersome to implement and can’t be easily generalized to data in higher dimensions. A better approach is that mentioned in my and WimC’s answers here: given the distance matrix D(i, j), define

M(i, j) = 0.5*(D(1, j)^2 + D(i, 1)^2 - D(i, j)^2)

which should be a positive semi-definite matrix with rank equal to the minimal Euclidean dimension k in which the points can be embedded. The coordinates of the points can then be obtained from the k eigenvectors v(i) of M corresponding to non-zero eigenvalues q(i): place the vectors sqrt(q(i))*v(i) as columns in an n x k matrix X; then each row of X is a point. In other words, sqrt(q(i))*v(i) gives the ith component of all of the points.

The eigenvalues and eigenvectors of a matrix can be obtained easily in most programming languages (e.g., using GSL in C/C++, using the built-in function eig in Matlab, using Numpy in Python, etc.)

Note that this particular method always places the first point at the origin, but any rotation, reflection, or translation of the points will also satisfy the original distance matrix.

More Related Contents:

  1. Calculate distance between 2 GPS coordinates
  2. Generate a random point within a circle (uniformly)
  3. How to determine if a list of polygon points are in clockwise order?
  4. A simple algorithm for polygon intersection
  5. Turning a cylinder into a sphere without pinching at the poles
  6. How to calculate the volume of a 3D mesh object the surface of which is made up triangles
  7. Cone to box collision
  8. How do I calculate the normal vector of a line segment? [closed]
  9. Calculating area enclosed by arbitrary polygon on Earth’s surface
  10. How do I combine complex polygons?
  11. Using atan2 to find angle between two vectors
  12. correcting fisheye distortion programmatically
  13. Implementing Ray Picking
  14. Signed angle between two 3D vectors with same origin within the same plane
  15. How do I detect intersections between a circle and any other circle in the same plane?
  16. Projecting 3D points to 2D plane [closed]
  17. How to distribute points evenly on the surface of hyperspheres in higher dimensions?
  18. Perpendicular on a line from a given point
  19. how map 2d grid points (x,y) onto sphere as 3d points (x,y,z)
  20. 3D coordinates on a sphere to Latitude and Longitude
  21. Calculate rotated rectangle size from known bounding box coordinates
  22. How to best approximate a geometrical arc with a Bezier curve?
  23. Get bounds of rotated rectangle
  24. Sort points in clockwise order?
  25. How do you calculate the average of a set of circular data? [closed]
  26. Smoothly connecting circle centers
  27. Is it safe to assume a GUID will always be unique?
  28. Nth Combination
  29. What is the standard (or best supported) big number (arbitrary precision) library for Lua?
  30. Draw a quadratic Bézier curve through three given points

Leave a Comment