Distance geometry
Distance geometry is the branch of mathematics concerned with characterizing and studying sets of points based only on given values of the distances between pairs of points.
[1][2][3] More abstractly, it is the study of semimetric spaces and the isometric transformations between them.
In this view, it can be considered as a subject within general topology.
[4] Historically, the first result in distance geometry is Heron's formula in 1st century AD.
The modern theory began in 19th century with work by Arthur Cayley, followed by more extensive developments in the 20th century by Karl Menger and others.
Distance geometry problems arise whenever one needs to infer the shape of a configuration of points (relative positions) from the distances between them, such as in biology,[4] sensor networks,[5] surveying, navigation, cartography, and physics.
The concepts of distance geometry will first be explained by describing two particular problems.Consider three ground radio stations A, B, C, whose locations are known.
The times it takes for a radio signal to travel from the stations to the receiver,
, and one needs to find out whether they lie within a low-dimensional affine subspace.
Now we formalize some definitions that naturally arise from considering our problems.
, we can arbitrarily specify the distances between pairs of points by a list of
Explicitly, we define a semimetric space as a nonempty set
The triangle inequality is omitted in the definition, because we do not want to enforce more constraints on the distances
In practice, semimetric spaces naturally arise from inaccurate measurements.
, they are defined to be affinely independent, iff they cannot fit inside a single
, they are affinely independent, since a generic n-simplex is nondegenerate.
For example, 3 points in the plane, in general, are not collinear, because the triangle they span does not degenerate into a line segment.
Similarly, 4 points in space, in general, are not coplanar, because the tetrahedron they span does not degenerate into a flat triangle.
be n + 1 points in a semimetric space, their Cayley–Menger determinant is defined by If
, then they make up the vertices of a possibly degenerate n-simplex
Thus Cayley–Menger determinants give a computational way to prove affine independence.
Cayley's 1841 paper studied the special case of
Brahmagupta's formula, from 7th century AD, generalizes it to cyclic quadrilaterals.
Tartaglia, from 16th century AD, generalized it to give the volume of tetrahedron from the distances between its 4 vertices.
The modern theory of distance geometry began with Arthur Cayley and Karl Menger.
[9][10] In 1931, Menger used distance relations to give an axiomatic treatment of Euclidean geometry.
[11] Leonard Blumenthal's book[12] gives a general overview for distance geometry at the graduate level, a large part of which is treated in English for the first time when it was published.
Thus, Cayley–Menger determinants give a concrete way to calculate whether a semimetric space can be embedded in
[5] Hyperbolic navigation is one pre-GPS technology that uses distance geometry for locating ships based on the time it takes for signals to reach anchors.
[4][12] Techniques such as NMR can measure distances between pairs of atoms of a given molecule, and the problem is to infer the 3-dimensional shape of the molecule from those distances.
