Euclidean distance geometry is, fundamentally, a determination of point conformation (configuration, relative position or location) by inference from interpoint distance information.  By inference we mean: eg, given only distance information, determine whether there corresponds a realizable conformation of points; a list of points in some dimension that attains the given interpoint distances.  Each point may represent simply location or, abstractly, any entity expressible as a vector in finite-dimensional Euclidean space.

It is a common misconception to presume that some desired point conformation cannot be recovered in the absence of complete interpoint distance information.  We might, for example, realize a constellation given only interstellar distance (or, equivalently, distance from Earth and relative angular measurement; the Earth as vertex to two stars).  At first it may seem O(N^2) data is required, yet there are many circumstances where this can be reduced to O(N).

If we agree that a set of points can have a shape three points can form a triangle and its interior, for example, four points a tetrahedron), then we can ascribe shape of a set of points to their convex hull.  It should be apparent: these shapes can be determined only to within a rigid transformation (a rotation, reflection, and a translation).

Absolute position information is generally lost, given only distance information, but we can determine the smallest possible dimension in which an unknown list of points can exist; that attribute is their affine dimension (a triangle in any ambient space has affine dimension 2, for example).  In circumstances where fixed points of reference are also provided, it becomes possible to determine absolute position or location.

Geometric problems involving distance between points can sometimes be reduced to convex optimization problems.  Mathematics of this combined study of geometry and optimization is rich and deep.  Its application has already proven invaluable discerning organic molecular conformation by measuring interatomic distance along covalent bonds.  Many disciplines have already benefitted and simplified consequent to this theory; eg, distance-based pattern recognition, localization in wireless sensor networks by measurement of intersensor distance along channels of communication, wireless location of a radio signal source such as a cell phone by multiple measurements of signal strength, the global positioning system (GPS), and multidimensional scaling which is a numerical representation of qualitative data by finding a low-dimensional scale.  Euclidean distance geometry has also found application in artificial  intelligence: to machine learning by discerning naturally occurring manifolds in Euclidean bodies, in Fourier spectra of kindred utterances, and in image sequences.

Read more...