# Creating a 2D map of objects given a sparse matrix of pairwise distances

I have a set of points on the two-dimensional plane, but their locations are not given to me. I am given the distance between some pairs of the points. However, I only know these differences for some pairs: I don't have every pairwise distance between the objects. I would like an algorithm to output the locations of the points.

The complication is that there could be some errors in the distances provided to me, so I want the algorithm to output a location for each point such that the pairwise distances between those locations match the provided distances as closely as possible.

Could anyone point me towards a method of computing a placement in 2-dimensional Euclidean space that would best solve this problem?

It would be nice to be able to provide hard constraints as well. For instance, I might be given that $C$ is exactly at the point $(1,2)$, or that all of the objects must fit in a $10 \times 10$ square. However, this is not strictly necessary: an algorithm that does not support hard constraints would still be interesting.

• The question is very unclear. What does "The distances are not exact, so there is no guarantee that they are satisfiable." exactly suggest? And what do you mean by "method of learning a placement"? What is that you want the algorithm to learn? May 28 '15 at 4:06
• I think what's given is the distance between some pairs of points, and we want the algorithm to output the locations (the $(x,y)$ coordinates) of each point. This is a computational geometry problem, not a machine learning problem, and it's typically solved by relaxation, mathematical optimization, spring models, or other techniques.
– D.W.
May 28 '15 at 4:57
• The distances aren't exact because they were estimated using RFID signals, so there is significant noise in the data; however, I would still like to know if there is some set of $(x,y)$ coordinates (as mentioned by D.W.) that best satisfies the set of distances we have.
– ncho
May 28 '15 at 8:43
• its a standard studied/ solved problem with many papers/ algorithms studying it, various implementations already built into real networks, and known as euclidean distance reconstruction from partial distance information
– vzn
Jun 27 '15 at 14:43