Distance geometry on arvau

Wikipedia / 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. 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 the 1st century AD. The modern theory began in the 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 networks, 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 navigationhyperbolic navigation

, from which the position of the receiver can be found.

Second problem: Dimensionality reductiondimension reduction

In data analysis, 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

. This defines a semimetric space: a metric space without triangle inequality.

if and only if .
.

Any metric space is a fortiori-dimensional Euclidean space, is the canonical metric space in distance geometry.

than the mere requirement that they be positive.

, violating the triangle inequality.

Isometric embedding

, an isometric embedding.

Affine independence

, they are defined to be affinely independent, iff-simplex.

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

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.

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

, then they make up the vertices of a possibly degenerate n. It can be shown that the n satisfies

, meaning the "0-dimensional volume" of a 0-simplex is 1, that is, there is 1 point in a 0-simplex.

. Thus Cayley–Menger determinants give a computational way to prove affine independence.

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 Arthur 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. 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:, 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 n + 1 points in the real numbers

be the k, then

then such an embedding exists.

are affinely independent.

Embedding n + 2 and n + 3 points

and

then such an embedding exists.

, the necessary and sufficient conditions are similar:

;

Embedding arbitrarily many points

case turns out to be sufficient in general.

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:

DGSOL. Solves large distance geometry problems in macromolecular modeling.
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 minimization).
TINKER. Molecular modeling and design. It can solve distance geometry problems.
SNLSDPclique. MATLAB code for locating sensors in a sensor network based on the distances between the sensors.