Distance geometry

From Wikipedia, the free encyclopedia

Distance geometry is the characterization and study of sets of points based only on given values of the distances between member pairs. Therefore distance geometry has immediate relevance where distance values are determined or considered, such as in surveying, cartography and physics.

[edit] Introduction

A straight line is the shortest path between two points. Therefore the distance from A to B is no bigger than the length of the straight-line path from A to C plus the length of the straight-line path from C to B. This fact is called the triangle inequality. If that sum happens to be equal to the distance from A to B, then the three points A, B, and C lie on a straight line, with C between A and B.

Similarly, suppose one knows

the distance from A to B;
the distance from A to C;
the distance from A to D;
the distance from B to C;
the distance from B to D; and
the distance from C to D.

Knowing only these six numbers, one would like to figure out

whether A, B, C, and D lie on a common straight line;
whether A, B, and C lie on a common line but D is not on that line (and similarly for any of A, B, and C in the role of the one exceptional point);
whether all four points lie in a common plane;
if they lie in a common plane, whether one of them is in the interior of the triangle formed by the other three, and if so, which one.

Distance geometry includes the solution of such problems.

[edit] Cayley-Menger determinants

Of particular utility and importance are classifications by means of Cayley-Menger determinants, named after Arthur Cayley and Karl Menger:

a set Λ (with at least three distinct elements) is called straight if

for any three elements A, B, and C of Λ holds

$\det \begin{bmatrix} 0 & d(AB)^2 & d(AC)^2 & 1 \\ d(AB)^2 & 0 & d(BC)^2 & 1 \\ d(AC)^2 & d(BC)^2 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix} = 0,$

a set Π (with at least four distinct elements) is called plane if

for any four elements A, B, C and D of Π,

$\det \begin{bmatrix} 0 & d(AB)^2 & d(AC)^2 & d(AD)^2 & 1 \\ d(AB)^2 & 0 & d(BC)^2 & d(BD)^2 & 1 \\ d(AC)^2 & d(BC)^2 & 0 & d(CD)^2 & 1 \\ d(AD)^2 & d(BD)^2 & d(CD)^2 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \end{bmatrix} = 0,$

but not all triples of elements of Π are straight to each other;

a set Φ (with at least five distinct elements) is called flat if

for any five elements A, B, C, D and E of Φ,

$\det \begin{bmatrix} 0 & d(AB)^2 & d(AC)^2 & d(AD)^2 & d(AE)^2 & 1 \\ d(AB)^2 & 0 & d(BC)^2 & d(BD)^2 & d(BE)^2 & 1 \\ d(AC)^2 & d(BC)^2 & 0 & d(CD)^2 & d(CE)^2 & 1 \\ d(AD)^2 & d(BD)^2 & d(CD)^2 & 0 & d(DE)^2 & 1 \\ d(AE)^2 & d(BE)^2 & d(CE)^2 & d(DE)^2 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 \end{bmatrix} = 0,$