Distance geometry.html

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.

1 Introduction
2 Cayley-Menger determinants
3 See also
4 External links

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.

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 iff, for any three elements A, B, and C of Λ,

$\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 iff, 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 iff, 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,$

but not all quadruples of elements of Φ are plane to each other;

and so on.

External links

Jon Dattorro, Convex Optimization & Euclidean Distance Geometry

GotLink

Distance geometry.html

Contents

Introduction

Cayley-Menger determinants

See also

External links