Optimal Discretization Orders for Distance Geometry: a Theoretical Standpoint
A. Mucherino

Distance geometry consists in embedding a simple weighted undirected graph G=(V,E,d) in a K-dimensional space so that all distances duv, which are the weights on the edges of G, are satisfied by the positions assigned to its vertices. The search domain of this problem is generally continuous, but it can be discretized under certain assumptions, that are strongly related to the order given to the vertices of G. This paper formalizes the concept of optimal partial discretization order, and adapts a previously proposed algorithm with the aim of finding discretization orders that are also able to optimize a given set of objectives. The objectives are conceived for improving the structure of the discrete search domain, for its exploration to become more efficient.