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 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 networks, surveying, navigation, cartography, and physics. The concepts of distance geometry will first be explained by describing two particular problems. 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. 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. Now we formalize some definitions that naturally arise from considering our problems. 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 , Positivity: if and only if . Symmetry: .