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?
Best Answer
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.