# Algorithm to construct all distances of a system described by $3N-6$ distances

A non-linear molecule has $3N-6$ degrees of freedom ($N$ is the number of atoms; ignoring translation and rotation). Therefore, a set of $3N-6$ distances and/or angles is enough, to describe the whole system.

I am searching for an algorithm, which takes $3N-6$ ($N$ is the number of points) distances as an input and calculates all ${{N(N-1)/2}}$ distances between all points.

• Some variants of this problem are computationally intractable (NP-hard), e.g., en.wikipedia.org/wiki/Distance_geometry_problem, mathoverflow.net/questions/7794 – Kirill Mar 5 '18 at 17:17
• When you say "$3N-6$ distances", do you mean just scalars, or vectors in some coordinate system? – Wolfgang Bangerth Mar 6 '18 at 13:17
• @WolfgangBangerth: just scalars (euclidean distances). – BudaTea Mar 6 '18 at 14:20
• As I understand the question, you can describe the system with $3N-6$ variables, therefore, you should find somewhere how these variables are connected and how to construct the points starting from the variables. Once you have the points you could get the distances. If what you say is true: 3N-6 entries can help you get all N(N-1)/2 distances, then there are additional relations which are satisfied by the geometry of the molecule. Without a complete description of the problem I don't think anyone can give you a full answer... – Beni Bogosel Mar 6 '18 at 19:41
• Does this mean you have $N\in \mathbb{Z^+}$ and you have given a set of $3N−6$ triples $(i_k,j_k,d_k), k\in \{1,\ldots,3N−6\}$, such that $i_k,j_k \in \{1,...,N\}, d_k>0, i_k<j_k$ and you want to find $N$ points $\{x_1,...,x_N\}$ in $\mathbb{R^3}$ such that $d(x_{i_k},x_{j_k})=d_{k}?$ – miracle173 May 11 '18 at 7:59

Assuming you can live with an approximate solution: you can re-formulate the problem as a graph embedding (or metric embedding) problem.

Your $N$ atoms $a_1,\dots,a_N$ are the vertices (nodes) of a graph $G$. For every pair of atoms $(a_i, a_j)$ for which you know a distance, you create an edge (link) in $G$. Now assign a length to each edge, using the known distance $d(a_i,a_j)$. Note that the edges in this graph will have nothing to do with the atomic bonds in your molecule, they are just there to capture the known distances.

Your task is to find an embedding $f: G \rightarrow R^3$ of the graph into the 3-dimensional space $R^3$, such that $dist(f(a_i), f(a_j))=d(a_i, a_j)$, where $dist$ is the actual euclidean distance in $R^3$.

One way to do that is to model the edges as springs, with lengths $d(a_i, a_j)$ and simulate the resulting mechanical system. Start with arbitrary positions of the atoms. At each time step compute the resulting force from all the springs that are attached to an atom. Move a little into that direction. Repeat. The system will come to rest at or near a solution of your problem (ignoring oscillations and such). Stopping criteria for the simulation might be: it (nearly) stops moving, total energy has reached a minimum, distances are close enough to the desired $d(a_i, a_j)$ etc.

Check out Force directed graph drawing, or just use some physics engine to simulate the whole thing. There is a bunch of literature about these kinds of simulations, how to optimize them, how to avoid getting stuck in local minima etc.

Regarding exact solutions, I'd suspect that you cannot get a closed-form solution, i.e. some formula that takes the $d(a_i, a_j)$ as input and produces valid positions of the atoms as outputs. Same for getting all the atom distances as outputs.

Similar to Berth's suggestion, you could fix one atom and try to minimize the function $$g(f)=\sum_{(i,j)\in G}\left[d(f_i,f_j)^2 -d_{ij}^2\right]^2$$ where $f$ is a matrix of 3D coords. This function is non-convex and should be optimized using a global optimization technique.