Distance geometry is the branch of mathematics concerned with
characterizing and studying
sets of points based ''only'' on given values of the
distance
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
s 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
In mathematics, general topology is the branch of topology that deals with the basic set-theoretic definitions and constructions used in topology. It is the foundation of most other branches of topology, including differential topology, geometr ...
.
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
Arthur Cayley (; 16 August 1821 – 26 January 1895) was a prolific British mathematician who worked mostly on algebra. He helped found the modern British school of pure mathematics.
As a child, Cayley enjoyed solving complex maths problems ...
, 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
In geometry, a position or position vector, also known as location vector or radius vector, is a Euclidean vector that represents the position of a point ''P'' in space in relation to an arbitrary reference origin ''O''. Usually denoted x, r, or ...
s) from the distances between them, such as in
biology
Biology is the scientific study of life. It is a natural science with a broad scope but has several unifying themes that tie it together as a single, coherent field. For instance, all organisms are made up of cells that process hereditary ...
,
sensor network,
surveying,
navigation,
cartography
Cartography (; from grc, χάρτης , "papyrus, sheet of paper, map"; and , "write") is the study and practice of making and using maps. Combining science, aesthetics and technique, cartography builds on the premise that reality (or an im ...
, 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,
, 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 reduction
Dimensionality reduction, or dimension reduction, is the transformation of data from a high-dimensional space into a low-dimensional space so that the low-dimensional representation retains some meaningful properties of the original data, ideally ...
In
data analysis
Data analysis is a process of inspecting, cleansing, transforming, and modeling data with the goal of discovering useful information, informing conclusions, and supporting decision-making. Data analysis has multiple facets and approaches, enc ...
, 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.
Definitions
Now we formalize some definitions that naturally arise from considering our problems.
Semimetric space
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