Editing Distance geometry

'''Distance geometry''' is the  branch of mathematics concerned with [[characterization (mathematics)|characterizing]] and studying [[Set (mathematics)|sets]] of points based ''only'' on given values of the [[distance]]s between pairs of points.<ref name="positioning" /><ref name="siam" /><ref name="DGAbook" /> More abstractly, it is the study of [[semimetric space]]s and the [[Isometry|isometric transformations]] between them. In this view, it can be considered as a subject within [[general topology]].<ref name="crippen" />

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 position]]s) from the distances between them, such as in [[biology]],<ref name="crippen" /> [[sensor network]]s,<ref name="sensors" /> [[surveying]], [[navigation]], [[cartography]], and [[physics]].

== Introduction and definitions ==
The concepts of distance geometry will first be explained by describing two particular problems.[[File:Hyperbolic_Navigation.svg|thumb|219x219px|Problem of hyperbolic navigation]]

=== 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, <math> t_A,t_B,t_C </math>, are unknown, but the time differences, <math>t_A-t_B </math> and <math>t_A-t_C </math>, are known. From them, one knows the distance differences <math>c(t_A-t_B) </math> and <math>c(t_A-t_C) </math>, from which the position of the receiver can be found.

=== Second problem: [[Dimensionality reduction|dimension reduction]]===
In [[data analysis]], one is often given a list of data represented as vectors <math>\mathbf{v} = (x_1, \ldots, x_n)\in \mathbb{R}^n</math>, 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 <math>R = \{P_0, \ldots, P_n\}</math>, <math>n \ge 0</math>, we can arbitrarily specify the distances between pairs of points by a list of  <math>d_{ij}> 0</math>, <math>0 \le i < j \le n</math>. This defines a [[Semi metric space|semimetric space]]: a metric space without [[triangle inequality]].

Explicitly, we define a semimetric space as a nonempty set <math>R</math> equipped with a semimetric <math>d: R\times R \to [0, \infty)</math> such that, for all <math>x, y\in R</math>,

# Positivity: <math>d(x, y) = 0</math> &nbsp; if and only if &nbsp;<math>x = y</math>.
# Symmetry: <math>d(x, y) = d(y, x)</math>.

Any metric space is [[Argumentum a fortiori|''a fortiori'']] a semimetric space. In particular, <math>\mathbb{R}^k</math>, the <math>k</math>-dimensional [[Euclidean space]], is the [[Canonical form|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 <math>d_{ij}</math> than the mere requirement that they be positive.

In practice, semimetric spaces naturally arise from inaccurate measurements. For example, given three points <math>A, B, C</math> on a line, with <math>d_{AB} = 1, d_{BC} = 1, d_{AC} = 2</math>, an inaccurate measurement could give <math>d_{AB} = 0.99, d_{BC} = 0.98, d_{AC} = 2.00</math>, violating the triangle inequality.

==== Isometric embedding ====
Given two semimetric spaces, <math>(R, d), (R', d')</math>, an [[Isometry|isometric embedding]] from <math>R</math> to <math>R'</math> is a map <math>f: R \to R'</math> that preserves the semimetric, that is, for all <math>x, y\in R</math>, <math>d(x, y) = d'(f(x), f(y))</math>.

For example, given the finite semimetric space <math>(R, d)</math> defined above, an isometric embedding from <math>R</math> to <math>\mathbb{R}^k</math> is defined by points <math display="inline">A_0, A_1,\ldots, A_n \in \mathbb R^k</math>, such that <math>d(A_i, A_j) = d_{ij}</math> for all <math>0 \le i < j \le n</math>.

==== Affine independence ====
Given the points <math display="inline">A_0, A_1,\ldots, A_n \in \mathbb R^k</math>, they are defined to be [[Affine independence|affinely independent]], [[iff]] they cannot fit inside a single <math>
l</math>-dimensional affine subspace of <math> \mathbb{R}^k</math>, for any <math> \ell < n</math>, iff the <math>n</math>''-''[[simplex]] they span, <math>v_n</math>, has positive <math>n</math>-volume, that is, <math>\operatorname{Vol}_n(v_n) > 0</math>.

In general, when <math>k\ge n </math>, they are affinely independent, since a [[Generic property|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 <math> n > k</math>, they must be affinely dependent. This can be seen by noting that any <math>n</math>-simplex that can fit inside <math>\mathbb{R}^k</math> must be "flat".

==Cayley–Menger determinants==
{{main|Cayley–Menger determinant}}
Cayley–Menger determinants, named after Arthur Cayley and Karl Menger, are determinants of matrices of distances between sets of points.

Let <math display="inline">A_0, A_1,\ldots, A_n</math> be ''n''&nbsp;+&nbsp;1 points in a semimetric space, their Cayley–Menger determinant is defined by

: <math>
\operatorname{CM}(A_0, \cdots, A_n) = \begin{vmatrix} 
0 & d_{01}^2 & d_{02}^2 & \cdots & d_{0n}^2 & 1 \\
d_{01}^2 & 0 & d_{12}^2 & \cdots & d_{1n}^2 & 1 \\
d_{02}^2 & d_{12}^2 & 0 & \cdots & d_{2n}^2 & 1 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
d_{0n}^2 & d_{1n}^2 & d_{2n}^2 & \cdots & 0 & 1 \\
1 & 1 & 1 & \cdots & 1 & 0
\end{vmatrix}</math>

If <math display="inline"> A_0, A_1,\ldots, A_n \in \mathbb R^k</math>, then they make up the vertices of a possibly [[Degeneracy (mathematics)|degenerate]] ''n''-simplex <math>v_n</math> in <math>\mathbb{R}^k</math>. It can be shown that<ref>{{Cite web|url=https://www.mathpages.com/home/kmath664/kmath664.htm|title=Simplex Volumes and the Cayley–Menger Determinant|website=www.mathpages.com|archive-url=https://web.archive.org/web/20190516033847/https://www.mathpages.com/home/kmath664/kmath664.htm|archive-date=16 May 2019|access-date=2019-06-08}}</ref> the ''n''-dimensional volume of the simplex <math>v_n</math> satisfies

: <math> \operatorname{Vol}_n(v_n)^2 = \frac{(-1)^{n+1}}{(n!)^2 2^n} \operatorname{CM}(A_0, \ldots, A_n). </math>

Note that, for the case of <math>n=0</math>, we have <math>\operatorname{Vol}_0(v_0) = 1</math>, meaning the "0-dimensional volume" of a 0-simplex is 1, that is, there is 1 point in a 0-simplex.

<math display="inline">A_0, A_1,\ldots, A_n</math> are affinely independent iff <math>\operatorname{Vol}_n(v_n) > 0</math>, that is, <math> (-1)^{n+1} \operatorname{CM}(A_0, \ldots, A_n) > 0</math>. Thus Cayley–Menger determinants give a computational way to prove affine independence.

If <math>
 k < n</math>, then the points must be affinely dependent, thus <math>
  \operatorname{CM}(A_0, \ldots, A_n) = 0</math>. Cayley's 1841 paper studied the special case of <math>
k = 3, n = 4</math>, that is, any five points <math>
A_0, \ldots, A_4</math> in 3-dimensional space must have <math>
\operatorname{CM}(A_0, \ldots, A_4) = 0</math>.

== 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 quadrilateral]]s. [[Niccolò Fontana Tartaglia|Tartaglia]], from 16th century AD, generalized it to give the [[Niccolò Fontana Tartaglia#Volume of a tetrahedron|volume of tetrahedron]] from the distances between its 4 vertices.

The modern theory of distance geometry began with [[Arthur Cayley]] and [[Karl Menger]].<ref>{{Cite journal|last1=Liberti|first1=Leo|last2=Lavor|first2=Carlile|date=2016|title=Six mathematical gems from the history of distance geometry|journal=International Transactions in Operational Research|language=en|volume=23|issue=5|pages=897–920|doi=10.1111/itor.12170|issn=1475-3995|arxiv=1502.02816|s2cid=17299562 }}</ref> Cayley published the Cayley determinant in 1841,<ref>{{Cite journal|last=Cayley|first=Arthur|date=1841|title=On a theorem in the geometry of position|journal=Cambridge Mathematical Journal|volume=2|pages=267–271}}</ref> 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]] <math>\mathbb{R}^n</math>.<ref>{{Cite journal|last=Menger|first=Karl|date=1928-12-01|title=Untersuchungen über allgemeine Metrik|journal=Mathematische Annalen|language=de|volume=100|issue=1|pages=75–163|doi=10.1007/BF01448840|s2cid=179178149 |issn=1432-1807}}</ref><ref name=":0">{{Cite journal|last1=Blumenthal|first1=L. M.|last2=Gillam|first2=B. E.|date=1943|title=Distribution of Points in ''n''-Space|url=https://www.tandfonline.com/doi/pdf/10.1080/00029890.1943.11991349|journal=The American Mathematical Monthly|language=en|volume=50|issue=3|pages=181|doi=10.2307/2302400|jstor=2302400}}</ref> In 1931, Menger used distance relations to give an axiomatic treatment of Euclidean geometry.<ref>{{Cite journal|last=Menger|first=Karl|date=1931|title=New Foundation of Euclidean Geometry|journal=American Journal of Mathematics|volume=53|issue=4|pages=721–745|doi=10.2307/2371222|issn=0002-9327|jstor=2371222}}</ref>

[[Leonard Blumenthal]]'s book<ref name="blumenthal" /> 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 (mathematics)|characterization theorem]] of semimetric spaces:<ref name="siam" /><blockquote>A semimetric space <math>(R, d)</math> is isometrically embeddable in the <math>n</math>-dimensional Euclidean space <math>\mathbb{R}^n</math>, but not in <math>\mathbb{R}^m</math> for any <math>0 \le m < n</math>, if and only if:

# <math>R</math> contains an <math>(n+1)</math>-point subset <math>S</math> that is isometric with an affinely independent <math>(n+1)</math>-point subset of <math>\mathbb{R}^n</math>;
# any <math>(n+3)</math>-point subset <math>S'</math>, obtained by adding any two additional points of <math>R</math> to <math>S</math>, is congruent to an <math>(n+3)</math>-point subset of <math>\mathbb{R}^n</math>.
</blockquote>A proof of this theorem in a slightly weakened form (for metric spaces instead of semimetric spaces) is in.<ref>{{Cite journal|last1=Bowers|first1=John C.|last2=Bowers|first2=Philip L.|s2cid=50040864|date=2017-12-13|title=A Menger Redux: Embedding Metric Spaces Isometrically in Euclidean Space|journal=The American Mathematical Monthly|volume=124|issue=7|pages=621|language=en|doi=10.4169/amer.math.monthly.124.7.621}}</ref>

== Characterization via Cayley–Menger determinants ==
The following results are proved in Blumethal's book.<ref name="blumenthal" />

=== Embedding ''n'' + 1 points in the real numbers ===
Given a semimetric space <math>
 (S,d)</math> , with <math>S = \{P_0, \ldots, P_n\}</math>, and  <math>d(P_i, P_j) = d_{ij}\ge 0</math>, <math>0 \le i < j \le n</math>, an isometric embedding of <math>(S, d)</math> into <math>\mathbb{R}^n</math> is defined by <math display="inline">A_0, A_1,\ldots, A_n \in \mathbb R^n</math>, such that <math>d(A_i, A_j) = d_{ij}</math> for all <math>0 \le i < j \le n</math>.

Again, one asks whether such an isometric embedding exists for <math>(S,d)</math>.

A necessary condition is easy to see: for all <math>k = 1, \ldots, n</math>, let <math>v_k</math> be the ''k''-simplex formed by  <math display="inline">A_0, A_1,\ldots, A_k</math>, then

:<math>(-1)^{k+1} \operatorname{CM}(P_0, \ldots, P_k) = (-1)^{k+1} \operatorname{CM}(A_0, \ldots, A_k) = 2^k (k!)^k \operatorname{Vol}_k(v_k)^2 \ge 0</math>

The converse also holds. That is, if for all <math>k = 1, \ldots, n</math>,

:<math>(-1)^{k+1}\operatorname{CM}(P_0, \ldots, P_k) \ge 0,</math>

then such an embedding exists.

Further, such embedding is unique up to isometry in <math>\mathbb{R}^n</math>. That is, given any two isometric embeddings defined by <math>A_0, A_1,\ldots, A_n</math>, and <math>A'_0, A'_1,\ldots, A'_n</math>, there exists a (not necessarily unique) isometry <math>T :  \mathbb R^n \to \mathbb R^n</math>, such that <math>T(A_k) = A'_k</math> for all <math>k = 0, \ldots, n</math>. Such <math>T</math> is unique if and only if <math>\operatorname{CM}(P_0, \ldots, P_n) \neq 0</math>, that is, <math>A_0, A_1,\ldots, A_n</math> are affinely independent.

=== Embedding ''n'' + 2 and ''n'' + 3 points ===
If <math>n+2</math> points <math>P_0, \ldots, P_{n+1}</math> can be embedded in <math>\mathbb{R}^n</math> as <math>A_0, \ldots, A_{n+1}</math>, then other than the conditions above, an additional necessary condition is that  the <math>(n+1)</math>-simplex formed by  <math>A_0, A_1,\ldots, A_{n+1}</math>, must have no <math>(n+1)</math>-dimensional volume. That is, <math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+1}) = 0</math>.

The converse also holds. That is, if for all <math>k = 1, \ldots, n</math>,

: <math>(-1)^{k+1} \operatorname{CM}(P_0, \ldots, P_k) \ge 0,</math>

and

: <math> \operatorname{CM}(P_0, \ldots, P_n, P_{n+1}) = 0, </math>

then such an embedding exists.

For embedding <math>n+3</math> points in <math>\mathbb{R}^n</math>, the necessary and sufficient conditions are similar:

# For all <math>k = 1, \ldots, n</math>, <math>(-1)^{k+1} \operatorname{CM}(P_0, \ldots, P_k) \ge 0</math>;
#<math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+1}) = 0;</math>
# <math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+2}) = 0;</math>
#<math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+1},  P_{n+2}) = 0.</math>

=== Embedding arbitrarily many points ===
The <math>n+3</math> case turns out to be sufficient in general.

In general, given a semimetric space <math>(R, d)</math>, it can be isometrically embedded in <math>\mathbb{R}^n</math> if and only if there exists <math>P_0, \ldots, P_n\in R</math>, such that, for all <math>k = 1, \ldots, n</math>, <math>(-1)^{k+1} \operatorname{CM}(P_0, \ldots, P_k) \ge 0</math>, and for any <math>P_{n+1}, P_{n+2} \in R</math>,

#<math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+1}) = 0;</math>
#<math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+2}) = 0;</math>
#<math>\operatorname{CM}(P_0, \ldots, P_n, P_{n+1},  P_{n+2}) = 0.</math>

And such embedding is unique up to isometry in <math>\mathbb{R}^n</math>.

Further, if <math>\operatorname{CM}(P_0, \ldots, P_n) \neq 0</math>, then it cannot be isometrically embedded in any <math>\mathbb{R}^m, m < n</math>. And such embedding is unique up to unique isometry in <math>\mathbb{R}^n</math>.

Thus, Cayley–Menger determinants give a concrete way to calculate whether a semimetric space can be embedded in <math>\mathbb{R}^n</math>, for some finite <math>n</math>, and if so, what is the minimal <math>n</math>.

==Applications==

There are many applications of distance geometry.<ref name=DGAbook/>

In telecommunication networks such as [[Global Positioning System|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.<ref name="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.<ref name="crippen" /><ref name="blumenthal" /> Techniques such as [[Nuclear magnetic resonance|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:

*[http://www.mcs.anl.gov/~more/dgsol/ DGSOL]. Solves large distance geometry problems in [[Molecular modelling|macromolecular modeling]].
*[http://nmr.cit.nih.gov/xplor-nih/ Xplor-NIH]. Based on [[X-PLOR]], to determine the structure of molecules based on data from NMR experiments. It solves distance geometry problems with heuristic methods (such as [[simulated annealing]]) and local search methods (such as [[conjugate gradient method|conjugate gradient minimization]]).
*[http://dasher.wustl.edu/tinker/ TINKER]. Molecular modeling and design. It can solve distance geometry problems.
*[https://sites.google.com/site/nathankrislock/software SNLSDPclique]. MATLAB code for locating sensors in a sensor network based on the distances between the sensors.

==See also==
* [[Euclidean distance matrix]]
* [[Multidimensional scaling]] (a statistical technique used when distances are measured with random errors)
* [[Metric space]]
* [[Tartaglia's formula]]
* [[Triangulation]]
* [[Trilateration]]

== References ==

{{Reflist|refs=

<ref name=sensors>
{{cite journal
|last1=Biswas
|first1=P.
|last2=Lian
|first2=T.
|last3=Wang
|first3=T.
|last4=Ye
|first4=Y.
|title=Semidefinite programming based algorithms for sensor network localization
|journal=ACM Transactions on Sensor Networks
|volume=2
|issue=2
|pages=188–220
|year=2006
|doi=10.1145/1149283.1149286
|s2cid=8002168
}}
</ref>

<ref name=blumenthal>
{{cite book 
|last=Blumenthal 
|first=Leonard M. 
|author-link=Leonard Blumenthal 
|title=Theory and Applications of Distance Geometry 
|publisher=Oxford University Press
|year=1953
|url=https://archive.org/details/theoryapplicatio0000leon/
|url-access=limited
}} ([https://archive.org/details/theoryapplicatio0000blum/ 2nd edition], Chelsea: 1970)
</ref>

<ref name=crippen>
{{cite book
|last1=Crippen
|first1=G.M.
|last2=Havel
|first2=T.F.
|title=Distance Geometry and Molecular Conformation
|publisher=John Wiley & Sons
|year=1988
}}
</ref>

<ref name=siam>
{{cite journal
| doi=10.1137/120875909
| title=Euclidean Distance Geometry and Applications
| journal=SIAM Review
| volume=56
| pages=3–69
| year=2014
| last1=Liberti
| first1=Leo
| last2=Lavor
| first2=Carlile
| last3=MacUlan
| first3=Nelson
| last4=Mucherino
| first4=Antonio
| arxiv=1205.0349
| s2cid=15472897
}}
</ref>

<ref name=DGAbook>
{{cite book
|last1=Mucherino
|first1=A.
|last2=Lavor
|first2=C.
|last3=Liberti
|first3=L.
|last4=Maculan
|first4=N.
|title=Distance Geometry: Theory, Methods and Applications
|url=https://archive.org/details/arxiv-1205.0349
|year=2013
}}
</ref>

<ref name=positioning>
{{cite journal
|last1=Yemini
|first1=Y.
|title=The positioning problem — a draft of an intermediate summary
|journal=Conference on Distributed Sensor Networks, Pittsburgh
|year=1978
}}
</ref>

}}

{{DEFAULTSORT:Distance Geometry}}
[[Category:Metric geometry]]
[[Category:Determinants]]