Open main menu

Distance geometry is the characterization and study of sets of points based only on given values of the distances between member pairs.[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 from the distances between them, such as in biology,[4] sensor network,[5] surveying, navigation, cartography, and physics.

Introduction and definitionsEdit

The concepts of distance geometry will first be explained by describing two particular problems.

 
Problem of hyperbolic navigation

First problem: hyperbolic navigationEdit

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,  , are unknown, but the time differences,   and  , are known. From them, one knows the distance differences   and  , from which the position of the receiver can be found.

Second problem: dimension reductionEdit

In data analysis, one is often given a list of data represented as vectors  , 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.

DefinitionsEdit

Now we formalize some definitions that naturally arise from considering our problems.

Semimetric spaceEdit

Given a list of points on  ,  , we can arbitrarily specify the distances between pairs of points by a list of  ,  . This defines a semimetric space: a metric space without triangle inequality.

Explicitly, we define a semimetric space as a nonempty set   equipped with a semimetric   such that, for all  ,

  1. Positivity:     if and only if   .
  2. Symmetry:  .

Any metric space is a fortiriori a semimetric space. In particular,  , the  -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   than the mere requirement that they be positive.

In practice, semimetric spaces naturally arises from inaccurate measurements. For example, given three points   on a line, with  , an inaccurate measurement could give  , violating the triangle inequality.

Isometric embeddingEdit

Given two semimetric spaces,  , an isometric embedding from   to   is a map   that preserves the semimetric, that is, for all  ,  .

For example, given the finite semimetric space   defined above, an isometric embedding into is defined by points  , such that   for all  .

Affine independenceEdit

Given the points  , they are defined to be affinely independent, iff they cannot fit inside a single  -dimensional affine subspace of  , for any  , iff the  -simplex they span,  , has positive  -volume, that is,  .

In general, when  , 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  , they must be affinely dependent. This can be seen by noting that any  -simplex that can fit inside   must be "flat".

Cayley–Menger determinantsEdit

Cayley–Menger determinants, named after Arthur Cayley and Karl Menger, are determinants of matrices of distances between sets of points.

Let   be n + 1 points in a semimetric space, their Cayley–Menger determinant is defined by

 

If  , then they make up the vertices of an (possibly degenerate) n-simplex   in  .It can be shown that[6] the n-dimensional volume of the simplex   satisfies

 .

Note that, for the case of  , we have  , meaning the "0-dimensional volume" of a 0-simplex is 1, that is, there is 1 point in a 0-simplex.

  are affinely independent iff  , that is,  . Thus Cayley–Menger determinants give a computational way to prove affine independence.

If  , then the points must be affinely dependent, thus  . Cayley's 1841 paper studied the special case of  , that is, any 5 points   in 3-dimensional space must have  .

HistoryEdit

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.[7] Cayley published the Cayley determinant in 1841[8], 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  .[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.

Menger characterization theoremEdit

Menger proved the following characterization theorem of semimetric spaces:[2]

A semimetric space   is isometrically embeddable in the  -dimensional Euclidean space  , but not in   for any  , if and only if:

  1.   contains an  -point subset   that is isometric with an affinely independent  -point subset of  ;
  2. any  -point subset  , obtained by adding any two additional points of   to  , is congruent to an  -point subset of  .

A proof of this theorem in a slightly weakened form (for metric spaces instead of semimetric spaces) is in [13].

Characterization via Cayley–Menger determinantsEdit

The following results are proved in Blumethal's book[12].

Embedding   points in  Edit

Given a semimetric space   , with  , and  ,  , an isometric embedding of   into   is defined by  , such that   for all  .

Again, one asks whether such an isometric embedding exists for  .

A necessary condition is easy to see: for all  , let   be the k-simplex formed by  , then

 

The converse also holds. That is, if for all  ,

 ,

then such an embedding exists.

Further, such embedding is unique up to isometry in  . That is, given any two isometric embeddings defined by  , and  , there exists a (not necessarily unique) isometry  , such that   for all  . Such   is unique if and only if  , that is,   are affinely independent.

Embedding   and   pointsEdit

If   points   can be embedded in   as  , then other than the conditions above, an additional necessary condition is that the  -simplex formed by  , must have no  -dimensional volume. That is,  .

The converse also holds. That is, if for all  ,

 ,

and

 ,

then such an embedding exists.

For embedding   points in  , the necessary and sufficient conditions are similar:

  1. For all  ,  ;
  2.  ;
  3.  ;
  4.  .

Embedding arbitrarily many pointsEdit

The   case turns out to be sufficient in general.

In general, given a semimetric space  , it can be isometrically embedded in   if and only if there exists  , such that, for all  ,  , and for any  ,

  1.  ;
  2.  ;
  3.  .

And such embedding is unique up to isometry in  .

Further, if  , then it cannot be isometrically embedded in any  . And such embedding is unique up to unique isometry in  .

Thus, Cayley–Menger determinants give a concrete way to calculate whether a semimetric space can be embedded in  , for some finite  , and if so, what is the minimal  .

ApplicationsEdit

There are many applications of distance geometry.[3]

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.[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.

There are many applications in chemistry.[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.

Some software packages for applications are:

See alsoEdit

ReferencesEdit

  1. ^ Yemini, Y. (1978). "The positioning problem — a draft of an intermediate summary". Conference on Distributed Sensor Networks, Pittsburgh.
  2. ^ a b Liberti, Leo; Lavor, Carlile; MacUlan, Nelson; Mucherino, Antonio (2014). "Euclidean Distance Geometry and Applications". SIAM Review. 56: 3–69. arXiv:1205.0349. doi:10.1137/120875909.
  3. ^ a b Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N. (2013). Distance Geometry: Theory, Methods and Applications.
  4. ^ a b c Crippen, G.M.; Havel, T.F. (1988). Distance Geometry and Molecular Conformation. John Wiley & Sons.
  5. ^ a b Biswas, P.; Lian, T.; Wang, T.; Ye, Y. (2006). "Semidefinite programming based algorithms for sensor network localization". ACM Transactions on Sensor Networks. 2 (2): 188–220. doi:10.1145/1149283.1149286.
  6. ^ "Simplex Volumes and the Cayley-Menger Determinant". www.mathpages.com. Archived from the original on 16 May 2019. Retrieved 2019-06-08.
  7. ^ Liberti, Leo; Lavor, Carlile (2016). "Six mathematical gems from the history of distance geometry". International Transactions in Operational Research. 23 (5): 897–920. arXiv:1502.02816. doi:10.1111/itor.12170. ISSN 1475-3995.
  8. ^ Cayley, Arthur (1841). "On a theorem in the geometry of position". Cambridge Mathematical Journal. 2: 267–271.
  9. ^ Menger, Karl (1928-12-01). "Untersuchungen über allgemeine Metrik". Mathematische Annalen (in German). 100 (1): 75–163. doi:10.1007/BF01448840. ISSN 1432-1807.
  10. ^ Blumenthal, L. M.; Gillam, B. E. (1943). "Distribution of Points in n-Space". The American Mathematical Monthly. 50 (3): 181. doi:10.2307/2302400. JSTOR 2302400.
  11. ^ Menger, Karl (1931). "New Foundation of Euclidean Geometry". American Journal of Mathematics. 53 (4): 721–745. doi:10.2307/2371222. ISSN 0002-9327. JSTOR 2371222.
  12. ^ a b c Blumenthal, L.M. (1970). Theory and applications of distance geometry (2nd ed.). Bronx, New York: Chelsea Publishing Company. pp. 90–161. ISBN 978-0-8284-0242-2. LCCN 79113117.
  13. ^ Bowers, John C.; Bowers, Philip L. (2017-12-13). "A Menger Redux: Embedding Metric Spaces Isometrically in Euclidean Space". The American Mathematical Monthly. 124 (7): 621. doi:10.4169/amer.math.monthly.124.7.621.