It has been a while I have not practiced mathematics but I should have enough background to get your answers if well detailed.

I have an n-by-n matrix, let's call it D, where dij represents the euclidian distance between Pi = (xi,yi) and Pj = (xj,yj). I want to find P1...Pn respecting those distances to place them on a graph to display to the user of my application.

I'm aware there not necessarily exists an exact solution (and not necessarily unic), therefore I'm only looking for a numeric solution. What approach do you propose ?

  • $\begingroup$ The points could all lie along the positive x axis I should think. Is that enough? $\endgroup$ – Paul Mar 19 '15 at 20:41
  • $\begingroup$ Let's take the following example : D = [ 0 1 10 ; 1 0 20 ; 10 20 0 ]. P1 should be close to P2 and far from P3 but P2 and P3 are far away from each other, so the best approximation with only one axis would be terrible. Plus, the aim is to display a graph so it must be readable for the user $\endgroup$ – Dici Mar 19 '15 at 21:05
  • $\begingroup$ With your D, if $P_1$ is at the origin then $P_2$ is on a circle radius 1, and $P_3$ is on a circle radius 10, both centre $P_1$. The distance of $P_2$ to $P_3$ cannot be 20, it is at most 11. You need a further condition on the numbers in your D matrix to take account of the triangle inequality involving distance in 2D, $d_{ij}\le d_{ik}+d_{kj}$. $\endgroup$ – Paul Mar 20 '15 at 10:33
  • $\begingroup$ Yes, this example shows that even a small problem cannot always have a good solution, but the point would be to minimize the error so that the order of magnitude is respected in order to provide a visually acceptable representation of the graph for the user $\endgroup$ – Dici Mar 20 '15 at 22:59

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.