Finding an Unknown Location with known distances from location

Question

Lets say that I have a map and an unknown location. If I have multiple locations in which I know the distance away from the unknown location, can I pinpoint the unknown location?

I am aware of Triangulation, but am looking for something that can be used if the distances from the unknown location are not very precise (i.e only a few decimal digits). Would it be possible to increase the accuracy of the determined unknown location by knowing the distances from the unknown location of many locations?

Answer 1

Absolutely. If you were able to determine the precise distance between the unknown point and a known point, you could picture that the unknown point is somewhere on a circle centered at the known point. With uncertainty, this circle becomes an annulus. By adding more known points, we intersect this annulus with other annuli to narrow it down to a small region. Each data point refines the region a little bit. After three measurements, you will be left with a shape roughly as big across as your error. Further measurements will give annuli which partially overlap this region, giving you even more accuracy. With enough accuracy, and assuming that your error is a random variable in some continuous distribution, you can achieve arbitrary accuracy.

I remember when I was a teenager, I had one of the first smartphones (it was big and slow, but it was hot stuff back then). I had a GPS app that could ping satellites to determine my location. It would tell me how many satellites I was connected to at any given time. I thought it interesting that it could tell my position with just three, but the accuracy kept going up with each additional satellite. This is the same sort of thing.

Answer 2

If you can quantify the imprecision it works similar to triangulation. If your known distances are say x km +- y km then you have a region they could be in.

For the first known point you have a ring with a given width. Once you add the second known point you have two regions they could be in. And so forth. Now adding more known points and their distances can help narrow the regions the point can be in assuming your imprecision isn't to large to make the extra information useless.

Answer 3

This problem is relevant from data reconciliation or nonlinear least square fit.

In cartesian coordinates, let us call $(X,Y,Z)$ the coordinates of the point $P$ we look for and $(x_i,y_i,z_i)$ the coordinates of the known points $Q_i$ (there are $n$ of them). The square of the distance between point $P$ and point $Q_i$ is given by $$D_i^2=(X-x_i)^2+(Y-y_i)^2+(Z-z_i)^2$$ while the measured distance is, say, $d_i$.

So, in the sense of least squares, the most natural function to minimize is $$\Phi(X,Y,Z)=\sum_{i=1}^n(D_i-d_i)^2$$ since what have been measured are the $d_i$'s and not their squares.

The problem is for sure nonlinear but good estimates can be found using spheres of radius $d_i$ with centers at $(x_i,y_i,z_i)$; their intersections gives a good idea of the approximate location of point $P$.

Personally, I am unable to do that (I am almost blind) and what I do is to take three points and consider the equation $$F_1=(X-x_1)^2+(Y-y_1)^2+(Z-z_1)^2-d_1^2=0$$ $$F_2=(X-x_2)^2+(Y-y_2)^2+(Z-z_2)^2-d_2^2=0$$ $$F_3=(X-x_3)^2+(Y-y_3)^2+(Z-z_3)^2-d_3^2=0$$ From here, develop $F_2-F_1$ and $F_3-F_1$; all terms $X^2,Y^2,Z^2$ disappear and then you have two linear equations in $Y,Z$ and you can express the solutions as linear functions of $X$. Plugging these into $F_1$ leads to a quadratic equation in $X$ so two roots $X_1,X_2$ for which you compute the corresponding $Y$ and $Z$ from the linear relations. So, you have your estimates $(X_1,Y_1,Z_1)$ and $(X_2,Y_2,Z_2)$ ; compute $\Phi(X_1,Y_1,Z_1)$ and $\Phi(X_2,Y_2,Z_2)$ and select the point corresponding to the lowest value.

Newton-Raphson method applied to the system of equations $\Phi'_X=\Phi'_Y=\Phi'_Z=0$ should converge in quite few iterations.

If you use latitudes and longitudes, the problem would be the same except that the parameters will be the latitude and longitude of point $P$; this reduces the number of parameters but the calculation of distances $D_i$ is slightly more complex.

More data points you will have, more accurate will be the location and standard statistical tests will give a good idea of the accuracy of the searched coordinates.

Application for illustration purposes

I selected seven points with coordinates and very approximates distances (rounded for two digits) given below $(x_i,y_i,z_i,d_i)$ $$\left( \begin{array}{cccc} 1 & 2 & +1 & 3.4 \\ 2 & 5 & -2 & 4.8 \\ 3 & 1 & -3 & 6.1 \\ 5 & 2 & +3 & 2.5 \\ 5 & 4 & -2 & 4.6 \\ 4 & 6 & +4 & 2.7 \\ 7 & 3 & +2 & 3.6 \end{array} \right) $$ and applied the procedure.

The results are
$$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ X & 3.51496 & 0.0224211 & \{3.45271,3.57722\} \\ Y & 3.87820 & 0.0244705 & \{3.81026,3.94614\} \\ Z & 2.37088 & 0.0190695 & \{2.31794, 2.42383\} \\ \end{array} $$ while the point used for the data generation was $X=3.5$, $Y=3.9$, $Z=2.4$ which is pretty accurate for distances in significant errors.

Using the shortcut method for the estimates, using the three points with largest distances, I had $X=3.588$, $Y=3.825$, $Z=2.374$. Quite close isn't it ?

Edit

For the initialization of parameters $(X,Y,Z)$, writing equations $$F_k=(X-x_k)^2+(Y-y_k)^2+(Z-z_k)^2-d_k^2=0$$ subtract one equation from all others to get $$2 (x_j-x_k)X+2 (y_j-y_k) Y+2 (z_j-z_k) Z=(x_j^2+y_j^2+z_j^2-d_j^2)-(x_k^2+y_k^2+z_k^2-d_k^2)$$ ($j=1,2,\cdots,n-1)$, $(k=j+1,j+2,\cdots,n)$ which then leads to a simple multilinear regression (with no intercept) by a simple definition of new regressors and function values. The system is easily solved using matrix calculations (for $n$ points, this gives $\frac{n(n-1)}2$ equations).

This being applied to the problem leads to $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ X & 3.52293 & 0.0118497 & \{3.49803,3.54782\} \\ Y & 3.85637 & 0.0129881 & \{3.82908,3.88366\} \\ Z & 2.37435 & 0.0089848 & \{2.35547, 2.39323\} \\ \end{array}$$

Please notice that we did not get the same answer because the two objective functions are different.

Edit

Let us rerun the same problem with very wrong data for the distances (using $3,5,6,2,5,3,4$). The obtained results are then $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ X & 3.22801 & 0.108367 & \{2.92713,3.52888\} \\ Y & 3.28107 & 0.136145 & \{2.90308,3.65907\} \\ Z & 2.61077 & 0.097509 & \{2.34004,2.88150\} \\ \end{array}$$ which are not so bad. With more data points, even with large errors, the results would be better.