Introduction

Consider a scenario where you are given only the pairwise distances between several milestones along a route. This data might come from various measurements collected during surveying or acquired via sensors. The challenge is to ascertain the exact positions of these milestones, which can have practical applications in fields such as cartography, robotics (for localization), and even computational biology (e.g., protein structure determination).

Problem Definition

Suppose you have `n` milestones, labeled as $M_1, M_2, \ldots, M_n$. The distances between these milestones are given in a distance matrix $D$, where $D_{i,j}$ represents the distance between $M_i$ and $M_j$. The goal is to determine the positions of these milestones in a coordinate space.

Technical Background

This problem can be framed as the "Distance Geometry Problem" (DGP), which is typically solved using techniques from linear algebra and optimization. Given a complete distance matrix, the aim is to recover a set of points such that their pairwise Euclidean distances match those specified in the matrix.

Requirements and Assumptions

• Distance Matrix: The matrix must be symmetric, i.e., $D_{i,j} = D_{j,i}$. • Triangle Inequality: To ensure distances are valid in a Euclidean space for three points $M_i$, $M_j$, and $M_k$, it must hold that $D_{i,j} + D_{j,k} \geq D_{i,k}$. • Feasibility: The problem must be feasible in the chosen dimensional space. For instance, in 2D, if $n = k+2$ points are needed to specify a space, you must ensure that $k+1$ independent distances cannot violate the condition of this space, i.e., they should form a 'rigid' configuration.

Algorithmic Solutions

Multidimensional Scaling (MDS)

A common approach to solve the positioning of milestones given pairwise distances is Multidimensional Scaling (MDS), particularly the metric classical MDS. It translates a matrix of distances into a set of coordinates in a lower-dimensional Euclidean space.

1. Double Centring: Compute the matrix $B = -0.5 \times J \times D \times J$, where $J = I - (1/n) \times \mathbf{1}\mathbf{1}^T$ and $\mathbf{1}$ denotes a vector of ones.
2. Eigen Decomposition: Perform eigen decomposition on matrix $B$ to find its eigenvalues and eigenvectors.
3. Scaling: Select the top `d` eigenvectors (where `d` is the dimension of the space you are reconstructing, e.g., 2 for a plane), scale them by the square roots of their corresponding eigenvalues to obtain coordinates in the desired dimensionality.

Example

Consider three milestones with matrix $D$:

• Point $M2$ is on the unit circle whose center is $M1$. • $M3$ is on a circle centered at $M1$ with radius 2 and at $M2$ with radius $\sqrt{3}$.