Carlile Lavor The distance geometry problem asks to find a realization of a given simple edge-weighted graph in a Euclidean space of given dimension K, where the edges are realized as straight segments of lengths equal (or as close as possible) to the edge weights. The problem is often modelled as a mathematical programming formulation involving decision … Read more
Distance Geometry is based on the inverse problem that asks to find the positions of points, in a Euclidean space of given dimension, that are compatible with a given set of distances. We briefly introduce the field, and discuss some open and promising research areas. ArticleDownload View PDF
The interval Distance Geometry Problem (iDGP) consists in finding a realization in R^K of a simple undirected graph G=(V,E) with nonnegative intervals assigned to the edges in such a way that, for each edge, the Euclidean distance between the realization of the adjacent vertices is within the edge interval bounds. Our aim is to determine … Read more
This is a partial account of the fascinating history of Distance Geometry. We make no claim to completeness, but we do promise a dazzling display of beautiful, elementary mathematics. We prove Heron’s formula, Cauchy’s theorem on the rigidity of polyhedra, Cayley’s generalization of Heron’s formula to higher dimensions, Menger’s characterization of abstract semi-metric spaces, a … Read more
When a weighted graph is an instance of the Distance Geometry Problem (DGP), certain types of vertex orders (called discretization orders) allow the use of a very efficient, precise and robust discrete search algorithm (called Branch-and-Prune). Accordingly, finding such orders is critically important in order to solve DGPs in practice. We discuss three types of … Read more
The Distance Geometry Problem in three dimensions consists in finding an embedding in R^3 of a given nonnegatively weighted simple undirected graph such that edge weights are equal to the corresponding Euclidean distances in the embedding. This is a continuous search problem that can be discretized under some assumptions on the minimum degree of the … Read more
Distance geometry problems arise from the need to position entities in the Euclidean $K$-space given some of their respective distances. Entities may be atoms (molecular distance geometry), wireless sensors (sensor network localization), or abstract vertices of a graph(graph drawing). In the context of molecular distance geometry, the distances are usually known because of chemical properties … Read more
The Hartree-Fock method is well known in quantum chemistry, and widely used to obtain atomic and molecular eletronic wave functions, based on the minimization of a functional of the energy. This gives rise to a multi-extremal, nonconvex, polynomial optimization problem. We give a novel mathematical programming formulation of the problem, which we solve by using … Read more