Distance Geometry - Introduction

Introduction

The Distance Geometry Problem (DGP) is the problem of finding the coordinates of a set of points starting from the distances between pairs of such points,,. Such a problem is nowadays much studied by the scientific community, because there are real-life applications that lead to the formulation of a DGP. As an example, an interesting application is the problem of locating sensors in telecommunication networks. In such a case, the positions of some sensors are known (which are called anchors) and some of the distances between sensors (which can be anchors or not) are known: the problem is to locate the positions of all the sensors.

Many other real-life applications that can be formulated as DGPs arise in biology and chemistry. For example, some models for protein predictions are based on a DGP, and also some models for protein docking. However, in this field, the most studied problem is the following: the coordinates of the atoms of a given molecular structure are determined by exploiting only some of the distances between pairs of atoms found by experimental techniques. If this is the case, the problem is known in the literature as the Molecular Distance Geometry Problem (MDGP).