2
$\begingroup$

Given is a triangle in the plane, with the coordinates of all three vertices known. I need to determine the location of a point $X$, for which the distances to all three triangle vertices are given (with some error). Therefore, $X$ is located at the intersection of the three circles around the triangle vertices, whose radii are the respective distances.

Since the distances are given with some error, the solution is not exact. How can the "best" intersection point be determined, possibly in a least-squares sense (e.g. minimizing the squared sum of deviations from the given distances)? Or is there a more reasonable way to define what is "best"?

2 Answers 2

2

You want $x$ that satisfies the three equations $ \|v_i - x \|^2 = d_i^2, $ but such an $x$ doesn't exist in general. We can ignore that technicality, and obtain two linear equations from these three, by subtracting the second and the third from the first: $ (v_2 - v_1)^T x = \frac{1}{2}[(d_1^2 -d_2^2) + (v_2^2 - v_1^2)] $ $ (v_3 - v_1)^T x = \frac{1}{2}[(d_1^2 -d_3^2) + (v_3^2 - v_1^2)], $ which can be written compactly in matrix form as $ V^Tx = w. $ Since the $v_i$ form a (presumably non-degenerate) triangle, $V$ is an invertible matrix, and we have a unique solution: $ x = V^{-T}w. $

I wasn't sure what this solution represented, but a friend supplied some insight. We can think of the triangle whose vertices are the $v_i$ as a triangle in a "weighted Delaunay triangulation". Unfortunately Wikipedia doesn't seem to have an entry on these yet. The dual diagram goes under various names, including "power diagram", "Laguerre diagram", "weighted Voronoi diagram", ...

Anyway, the point $x$ that we are finding is a vertex in the power diagram, where the weights on the $v_i$ are the $d_i$. It is the centre of the unique circle that intersects the circles $C(v_i,d_i)$ orthogonally. The caveat is that this 'circle' may have an imaginary radius.

In other words, if we take the three initial equations and add a third parameter, $h$, then the equations $ \|v_i - x \|^2 = d_i^2 + h, $ do admit a unique solution, where $h$ is the square of the radius of the orthogonal circle (some people call this the orthocircle, but its centre is not the usual orthocentre.)

I do not know whether this point is the same as you would find with Robert's optimization suggestion. Presumably this point can be characterized as an optimal solution of some functional.

  • 1
    I found that confusing too. The fact is we are solving a system of equations that *does* have a solution, namely the three equations with the extra parameter $h$ added. The $h$ is probably a reasonable indicator of your "error".2011-05-17
1

If the points are $v_1$ to $v_3$ and the given distances are $d_1$ to $d_3$, you might try finding the point $p$ to minimize $f(p) = \sum_i (\|p - v_i\|^2 - d_i^2)^2$. This objective function is smooth, avoiding differentiability problems that might bother some solvers.