2
$\begingroup$

Given a set of points in a plane, and series of measurements of the distances between those points, how would I go about generating a best-fit model of the position of the points?

For example, given 3 points (A, B, C) that define a 30-40-50 right triangle, the data set might look something like this:

(0, 29.1, 39.7) - at point A, measuring to B, C
(NULL, 0, 49.4) - at point B, missing measurement to A
(40.4, 50.5, 0) - at point C, measuring to A, B

What I would like to do is fit this data to a model that will make it possible to determine the distance between any two arbitrary data points, as well as determine the error (given a known error in each measurement). I'm not even sure what type of problem this is, so any pointers to methods or algorithms would be greatly appreciated.

$\endgroup$
2
$\begingroup$

If you know that you have $n$ points $X_1,...,X_n$ and the desired pairwise distances $d_{ij}$ between $X_i$ and $X_j$ you could try and optimize the functional $$ \sum_{i<j} (d_{ij}-|X_i-X_j|)^2$$

In my opinion this looks good as an optimization problem. You can compute the gradient explicitly (even the Hessian, if you are motivated) and then use some Newton or quasi-Newton solver to find an optimizer.

Of course, you could use a $p$-norm in stead of the $2$-norm above. For $p$ large it will try to minimize the largest error.

It remains to be seen if it works well. This may depend on the choice of the initial condition. Multiple starts from random initializations may help avoid local minima...

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

This is an application of Euclidean Distance Matrices. Here's a good overview of the problem, including some algorithms for solving it.

Abstract: https://arxiv.org/abs/1502.07541 Full article: https://arxiv.org/pdf/1502.07541

| cite | improve this answer | |
$\endgroup$

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.