Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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"?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
Very nice, this sounds pretty straight-forward. I am going to mark this as an answer. One thing, however, I do not quite understand: how is it that a solution $x$ pops out from an equation system that has no solution to begin with? Somewhere probably there is a step that is not reversible, but I can't seem to find it. –  koletenbert May 17 '11 at 17:59
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". –  yasmar May 17 '11 at 20:31

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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