Reliable Computation of Coordinates From Distance Information
by
Ian Coope
University of Canterbury

The problem of determining the points of intersection of n spheres in Rⁿ has many applications. Examples in 3-D include problems in navigation, in positioning of specific atoms in crystal structures, in reconstructing torso geometries in experimental cardiology, in the `Pentacle Problem, ' and in many other problems of distance geometry. The problem is easily formulated as a system of n nonlinear equations in the coordinates of the unknown point(s) of intersection and it is of interest to determine an efficient and reliable method of solution. It is shown that apart from a few square roots the problem is usually easily and robustly solved without iteration by employing standard techniques from linear algebra. In some applications, however, the radii of the spheres may not be known accurately and this can lead to difficulties, particularly when the required point is close to lying in the affine subspace defined by the n given points. In such cases it is more appropriate to formulate a nonlinear least squares problem in order to identify a `best approximate solution.' The special structure of this nonlinear least squares problem allows a solution to be calculated through an efficient safeguarded Newton iteration.

Date received: August 1, 1999