Distance geometry

Distance geometry is the characterization and study of sets of points based "only" on given values of the distances between member pairs. 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.
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, sensor network, surveying, navigation, cartography, and physics.
Introduction and definitions.
The concepts of distance geometry will first be explained by describing two particular problems.
First problem: hyperbolic navigation.
Consider three ground radio stations A, B, C, whose locations are known. A radio receiver is at an unknown location. The times it takes for a radio signal to travel from the stations to the receiver, formula_1, are unknown, but the time differences, formula_2 and formula_3, are known. From them, one knows the distance differences formula_4 and formula_5, from which the position of the receiver can be found.
Second problem: dimension reduction.
In data analysis, one is often given a list of data represented as vectors formula_6, and one needs to find out whether they lie within a low-dimensional affine subspace. A low-dimensional representation of data has many advantages, such as saving storage space, computation time, and giving better insight into data.
Definitions.
Now we formalize some definitions that naturally arise from considering our problems.
Semimetric space.
Given a list of points on formula_7, formula_8, we can arbitrarily specify the distances between pairs of points by a list of formula_9, formula_10. This defines a semimetric space: a metric space without triangle inequality.
Explicitly, we define a semimetric space as a nonempty set formula_11 equipped with a semimetric formula_12 such that, for all formula_13,
Any metric space is "a fortiori" a semimetric space. In particular, formula_17, the formula_18-dimensional Euclidean space, is the canonical metric space in distance geometry.
The triangle inequality is omitted in the definition, because we do not want to enforce more constraints on the distances formula_19 than the mere requirement that they be positive.
In practice, semimetric spaces naturally arises from inaccurate measurements. For example, given three points formula_20 on a line, with formula_21, an inaccurate measurement could give formula_22, violating the triangle inequality.
Isometric embedding.
Given two semimetric spaces, formula_23, an isometric embedding from formula_11 to formula_25 is a map formula_26 that preserves the semimetric, that is, for all formula_13, formula_28.
For example, given the finite semimetric space formula_29 defined above, an isometric embedding into is defined by points formula_30, such that formula_31 for all formula_10.
Affine independence.
Given the points formula_33, they are defined to be affinely independent, iff they cannot fit inside a single formula_34-dimensional affine subspace of formula_35, for any formula_36, iff the formula_37"-"simplex they span, formula_38, has positive formula_37-volume, that is, formula_40.
In general, when formula_41, 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.
When formula_42, they must be affinely dependent. This can be seen by noting that any formula_37-simplex that can fit inside formula_17 must be "flat".
Cayley–Menger determinants.
Cayley–Menger determinants, named after Arthur Cayley and Karl Menger, are determinants of matrices of distances between sets of points.
Let formula_45 be "n" + 1 points in a semimetric space, their Cayley–Menger determinant is defined by
formula_46
If formula_33, then they make up the vertices of an (possibly degenerate) n-simplex formula_48 in formula_17. It can be shown that the n-dimensional volume of the simplex formula_48 satisfies
formula_51.
Note that, for the case of formula_52, we have formula_53, meaning the "0-dimensional volume" of a 0-simplex is 1, that is, there is 1 point in a 0-simplex.
formula_45 are affinely independent iff formula_40, that is, formula_56. Thus Cayley–Menger determinants give a computational way to prove affine independence.
If formula_57, then the points must be affinely dependent, thus formula_58. Cayley's 1841 paper studied the special case of formula_59, that is, any 5 points formula_60 in 3-dimensional space must have formula_61.
History.
The first result in distance geometry is Heron's formula, from 1st century AD, which gives the area of a triangle from the distances between its 3 vertices. 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 Authur Cayley and Karl Menger. Cayley published the Cayley determinant in 1841, which is a special case of the general Cayley–Menger determinant. Menger proved in 1928 a characterization theorem of all semimetric spaces that are isometrically embeddable in the "n"-dimensional Euclidean space formula_62. In 1931, Menger used distance relations to give an axiomatic treatment of Euclidean geometry.
Leonard Blumenthal's book 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.
Menger characterization theorem.
Menger proved the following characterization theorem of semimetric spaces:A semimetric space formula_29 is isometrically embeddable in the formula_37-dimensional Euclidean space formula_62, but not in formula_66 for any formula_67, if and only if:
A proof of this theorem in a slightly weakened form (for metric spaces instead of semimetric spaces) is in.
Characterization via Cayley–Menger determinants.
The following results are proved in Blumethal's book.
Embedding formula_79 points in formula_62.
Given a semimetric space formula_81 , with formula_82, and formula_83, formula_10, an isometric embedding of formula_85 into formula_62 is defined by formula_87, such that formula_31 for all formula_10.
Again, one asks whether such an isometric embedding exists for formula_81.
A necessary condition is easy to see: for all formula_91, let formula_92 be the "k"-simplex formed by formula_93, then
formula_94
The converse also holds. That is, if for all formula_91,
formula_96,
then such an embedding exists.
Further, such embedding is unique up to isometry in formula_62. That is, given any two isometric embeddings defined by formula_45, and formula_99, there exists a (not necessarily unique) isometry formula_100, such that formula_101 for all formula_102. Such formula_103 is unique if and only if formula_104, that is, formula_45 are affinely independent.
Embedding formula_106 and formula_107 points.
If formula_106 points formula_109 can be embedded in formula_62 as formula_111, then other than the conditions above, an additional necessary condition is that the formula_69-simplex formed by formula_113, must have no formula_69-dimensional volume. That is, formula_115.
The converse also holds. That is, if for all formula_91,
formula_96,
and
formula_115,
then such an embedding exists.
For embedding formula_107 points in formula_62, the necessary and sufficient conditions are similar:
Embedding arbitrarily many points.
The formula_107 case turns out to be sufficient in general.
In general, given a semimetric space formula_29, it can be isometrically embedded in formula_62 if and only if there exists formula_129, such that, for all formula_91, formula_96, and for any formula_132,
And such embedding is unique up to isometry in formula_62.
Further, if formula_104, then it cannot be isometrically embedded in any formula_138. And such embedding is unique up to unique isometry in formula_62.
Thus, Cayley–Menger determinants give a concrete way to calculate whether a semimetric space can be embedded in formula_62, for some finite formula_37, and if so, what is the minimal formula_37.
Applications.
There are many applications of distance geometry.
In telecommunication networks such as GPS, the positions of some sensors are known (which are called anchors) and some of the distances between sensors are also known: the problem is to identify the positions for all sensors. 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.
There are many applications in chemistry. 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.
Some software packages for applications are: