Speaker
Description
The Distance Geometry Problem (DGP) asks whether a simple weighted undirected graph G=(V,E,d) can be realized in the K-dimensional Euclidean space so that the distance constraints implied by the weights on the graph edges are satisfied. This problem was proven to be NP-hard in the context of graph embeddability, and has several applications. In this talk, we will focus on various currently ongoing works in this very rich research context: (1) We will talk about a particular class of DGP instances where, under particular assumptions, it is possible to represent the search space as a binary tree, and where in ideal situations, vertex positions can be assigned to each of its nodes. In real-life applications, however, the distances are generally provided with low precision, and they are actually likely to carry measurement errors, so that local continuous search spaces are actually assigned to each tree node. This gives rise to special combinatorial problems which are locally continuous. (2) We will review the main applications of the DGP, ranging from structural biology, passing through sensor network localization and adaptive maps, until the dynamical component is included in DGP instances for computer graphics applications. (3) Finally, we present an alternative computing approach for the solution of the DGPs in dimension 1, where an analog optical processor is employed for the computations, which is based on some properties of laser light beams.
