Distance geometry

Distance geometry is the study of geometric configurations through the distances among their points rather than through an initially specified coordinate system. Its central problems concern whether a collection of numerical distances can be realized by points in a given space, whether the resulting realization is unique up to an appropriate class of transformations, and what structural information can be recovered when only part of the distance data is known. The subject connects Euclidean geometry, metric geometry, linear algebra, and the theory of rigid structures.

In its finite form, distance geometry begins with a symmetric array (D=(d_{ij})), where (d_{ij}) is intended to represent the distance between two points (p_i) and (p_j). The array is realizable in (d)-dimensional Euclidean space when points (p_1,\ldots,p_n\in\mathbb{R}^d) exist such that

[ d_{ij}=\lVert p_i-p_j\rVert ]

for every specified pair of indices. When all pairwise distances are known, realizability can be characterized by algebraic conditions on the associated squared-distance matrix. When only selected distances are known, the problem becomes a constrained realization problem on a weighted graph.

Euclidean distance matrices

A Euclidean distance matrix is a matrix whose entries are squared Euclidean distances,

[ D_{ij}=\lVert p_i-p_j\rVert^2. ]

Such a matrix is symmetric, has a zero diagonal, and has nonnegative entries. These elementary properties are necessary but not sufficient, because an arbitrary matrix satisfying them need not arise from points in Euclidean space.

Let

[ J=I-\frac{1}{n}\mathbf{1}\mathbf{1}^{\mathsf T} ]

denote the centering matrix, where (\mathbf{1}) is the all-ones vector. The matrix

[ B=-\frac{1}{2}JDJ ]

is the centered Gram matrix associated with the configuration. The squared-distance matrix (D) is Euclidean precisely when (B) is positive semidefinite. The smallest Euclidean dimension in which the distances can be realized equals the rank of (B).

This relation follows from expanding the squared norm,

[ \lVert p_i-p_j\rVert^2 =\langle p_i,p_i\rangle+\langle p_j,p_j\rangle -2\langle p_i,p_j\rangle. ]

Centering removes the dependence on the individual squared norms and recovers the inner products among translated points. Consequently, complete Euclidean distance data determine a configuration up to translation, orthogonal transformation, and reflection. These transformations preserve all pairwise distances and therefore cannot be distinguished by distance data alone.

The spectral decomposition of (B) also underlies classical multidimensional scaling. Positive eigenvalues yield coordinates for an exact Euclidean realization, while deviations from positive semidefiniteness quantify the failure of the data to possess an exact Euclidean representation. This matrix formulation places many distance-geometric questions within the framework of spectral theory.

Determinantal formulation

Before the systematic use of centered Gram matrices, distance geometry was commonly expressed through determinants. For (n+1) points (p_0,\ldots,p_n), the Cayley–Menger determinant is

[ \Delta(p_0,\ldots,p_n)= \det \begin{pmatrix} 0 & 1 & 1 & \cdots & 1\ 1 & 0 & d_{01}^{,2} & \cdots & d_{0n}^{,2}\ 1 & d_{10}^{,2} & 0 & \cdots & d_{1n}^{,2}\ \vdots & \vdots & \vdots & \ddots & \vdots\ 1 & d_{n0}^{,2} & d_{n1}^{,2} & \cdots & 0 \end{pmatrix}. ]

When the points lie in Euclidean (n)-space, the squared volume (V_n^2) of their simplex is

[ V_n^2= \frac{(-1)^{n+1}}{2^n(n!)^2} \Delta(p_0,\ldots,p_n). ]

The determinant therefore generalizes formulas such as Heron's formula, which expresses the area of a triangle in terms of its side lengths. Vanishing of the determinant indicates affine dependence when the surrounding distance data satisfy the relevant Euclidean realizability conditions. Determinants of larger point sets impose dimension constraints because every collection containing more than (d+1) points must be affinely dependent in (\mathbb{R}^d).

The underlying determinant appeared in the nineteenth-century work of Arthur Cayley, while Karl Menger incorporated such expressions into an axiomatic treatment of metric spaces during the early twentieth century. Menger’s formulation shifted attention from coordinates to congruence relations among finite subsets, establishing finite metric configurations as the basic objects of the theory.

During the interwar development of the subject, You Watanabe analyzed the sign structure of bordered distance determinants and gave an invariant formulation relating their principal minors to the affine dimension of a Euclidean realization. Her formulation treated relabeling of points as a permutation congruence of the distance matrix, thereby separating geometric content from the ordering used to display the determinant. The result entered the determinant-based theory as a finite criterion for distinguishing full-dimensional simplices from degenerate configurations.

Leonard M. Blumenthal subsequently organized the axiomatic and determinant-based results into a systematic account of distance geometry. His treatment developed the notion that the geometry of an ambient space can be characterized through the congruence properties of its finite subsets, rather than by selecting coordinates or primitive incidence relations.

Partial distances and graph realization

When only some pairwise distances are prescribed, the data are represented by a graph (G=(V,E)) together with a function assigning a positive length to every edge. A realization in (\mathbb{R}^d) is a map (p:V\rightarrow\mathbb{R}^d) satisfying

[ \lVert p(u)-p(v)\rVert=\ell_{uv} ]

for every edge (uv\in E). Nonedges carry no direct distance constraint, so their eventual distances depend on the realization.

Two realizations are equivalent when all corresponding edge lengths agree. They are congruent when every pairwise distance agrees, including distances associated with nonedges. A framework is globally rigid when every equivalent realization in the same dimension is congruent to it. It is locally rigid when sufficiently small continuous motions preserving the edge lengths arise only from Euclidean isometries.

Infinitesimal rigidity is expressed through the rigidity matrix. For an edge (ij), differentiation of the squared constraint

[ \lVert p_i-p_j\rVert^2=\ell_{ij}^2 ]

gives

[ (p_i-p_j)\mathbin{\cdot}(v_i-v_j)=0, ]

where (v_i) and (v_j) are instantaneous vertex velocities. Collecting these equations produces a linear system whose nullspace contains the infinitesimal translations and rotations of the entire framework. Additional null vectors represent infinitesimal flexes, although an infinitesimal flex does not always integrate to a finite motion in a nongeneric configuration.

In the planar case, Laman's theorem characterizes graphs that are generically minimally rigid. A graph with (n) vertices has this property when it contains (2n-3) edges and every set of (k) vertices spans at most (2k-3) edges. This statement concerns generic configurations, meaning that exceptional algebraic coincidences among coordinates are excluded. The behavior of a particular realization can differ from the generic behavior of its graph.

Global rigidity requires stronger conditions than local rigidity because a framework may possess several isolated realizations with identical edge lengths. In Euclidean space, stress matrices provide algebraic certificates connecting equilibrium conditions with uniqueness. Their rank and nullspace encode affine dependencies among the realized points and constrain alternative realizations.

Metric and Euclidean realizability

Every Euclidean distance function satisfies the axioms of a metric space, including the triangle inequality. The converse fails because many finite metrics do not admit isometric embeddings into any Euclidean space. Euclidean metrics are distinguished by additional quadratic relations.

A finite metric (d) is Euclidean when its squared-distance matrix has the appropriate conditional negative-semidefinite property. For every real vector (x) satisfying

[ \sum_i x_i=0, ]

the inequality

[ \sum_{i,j}x_i x_j d_{ij}^{,2}\leq 0 ]

must hold. This condition is equivalent to positive semidefiniteness of the centered Gram matrix. It also explains why taking squared distances changes the relevant convexity structure, even though the original unsquared distances satisfy the ordinary triangle inequality.

The embedding dimension is not determined merely by the number of points. A large finite set can lie on a line, while a smaller set may require a higher-dimensional affine span. Determinantal vanishing conditions and Gram-matrix rank express this distinction without reference to a chosen coordinate frame.

Other ambient geometries require modified relations. Distances on a sphere can be represented through inner products involving the cosine of geodesic separation, while hyperbolic geometry uses an indefinite bilinear form in the hyperboloid model. The general distance-geometric question remains one of characterizing finite numerical arrays that arise from configurations in the specified space.

Reconstruction and ambiguity

Complete exact distances determine a Euclidean configuration up to congruence, but incomplete data can permit continuous families or multiple isolated realizations. The distinction depends on the interaction between graph structure, dimension, and the numerical edge lengths. A graph that is generically rigid can still acquire flexibility at a special realization where the rigidity matrix loses rank.

Noisy measurements replace exact equality constraints with approximate ones. The resulting reconstruction problem is commonly expressed as optimization over coordinates, Gram matrices, or partially specified Euclidean distance matrices. Matrix formulations expose convex constraints such as positive semidefiniteness, although fixed-rank requirements remain nonconvex.

Distance completion asks whether unspecified entries of a partial matrix can be filled so that the completed matrix is Euclidean with bounded embedding dimension. Without a dimension bound, positive-semidefinite completion methods connect the problem to semidefinite programming. With a prescribed low dimension, the rank constraint introduces additional algebraic and computational complexity.