3
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Dipped Bits May 28 '15 at 4:06
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ May 28 '15 at 4:57
  • $\begingroup$ 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. $\endgroup$ – ncho May 28 '15 at 8:43
  • $\begingroup$ 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 $\endgroup$ – vzn Jun 27 '15 at 14:43
1
$\begingroup$

This is known as "graph layout" or "graph drawing" (practical methods) or "graph embedding" (theoretical interest). The relevant techniques are more closely associated with computational geometry and mathematical optimization, not machine learning. See this Wikipedia article and Recovering a point embedding from a graph with edges weighted by point distance and Efficient algorithm to fulfil a set of coordinate constraints for an overview of some standard techniques. Pairwise comparisons with confidence might also have some helpful techniques (it is focused on the 1D case, not the 2D case, but it might be possible to generalize Yuval's answer to the 2D case as well).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I'll take a look at the links. Thanks for the pointers! $\endgroup$ – ncho May 28 '15 at 8:44

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.