5
$\begingroup$

For a $n$-polygon in $\mathbb{R}^3$ the set of distances between all pairs of vertices is given. (How) is it possible to reconstruct the geometric structure of the polygone?

Symbolically: For a set of coordinates $(x_i,y_i,z_i)$ with $i=1,...,n$ we have given $r_{k} = (x_i -x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2$, for $k = 1,...,n(n-1)/2$ without knowing the map $k\rightarrow (i,j)$ and want to know the set of $(x_i,y_i,z_i)$.

It seems clear, that the distances between the points determine the polygon only up to translations and rotations. So we are seeking to determine only 3$n$-6 degrees of freedom and we have $n(n-1)/2$ equations. As well the coordinates are at most determined up to an arbitrary permutation. The question of the assignment of the distances to actual vertices seems a key in the solution.

I have absolutely now clue as to how address the question, I guess the answer will somehow involve group theory.

It is motivated by the determination of molecular structures using diffraction
methods. Its a kind of toy-version (all elements the same) of the so called inverse structure problem. I am doing experimental research on this subject. It is usually solved using model structures (you just assume the type of polygon including the mapping between $k$ and $(i,j)$ and fit the structure parameters (coordinates) to the diffraction data).

(I am also clueless about the correct tags for the disciplines that involves, so sorry for wrong guesses in case).

Improve this question
$\endgroup$
4
  • $\begingroup$ It seems to me that you can construct the triangle $p_1,p_2,p_3$ in whatever orientation you like pretty easily. Then for any other point $p_k$, you have one or two choices for where it must land depending on which side of the initial plane you are looking at. So it does not seem that hard? $\endgroup$
    – Steven Gubkin
    Commented Dec 11, 2015 at 18:23
  • $\begingroup$ Maybe it should be added that one does know the distances only up to a arbitrary permutation of the indices and that an analytic solution of the equations is sought. $\endgroup$
    – Raphael J.F. Berger
    Commented Dec 11, 2015 at 18:46
  • $\begingroup$ The question you asked does not indicate anything about "arbitrary permutations". Can you make that more precise? Do you mean that you have a set of distances between vertices, without knowing which distances go with which vertices? $\endgroup$
    – Steven Gubkin
    Commented Dec 11, 2015 at 18:51
  • 1
    $\begingroup$ See the earlier MO question on "Difference sets," and the beltway reconstruction problem for several references, and this even earlier MO question, "Feasibility of a list of prescribed distances in R^3" on distance geometry. You'll see there is an entire book on Distance geometry and molecular conformation. $\endgroup$
    – Joseph O'Rourke
    Commented Dec 11, 2015 at 19:33

2 Answers 2

Reset to default
1
$\begingroup$

A related question is as follows: Let $P$ be a polytope in $\mathbb{R}^n$, with say integer vertices.

Consider the new Laurent generating function $$F(x) = \sum_{p,q \in P} x^{p-q}$$, where the sum ranges over all vertices of $P$ (or maybe lattice points of $P$), with the convention $x^a = x_1^{a_1} \dotsm x_n^{a_n}$. Note that $F(x)$ encodes all information you are given, and a bit more.

Is it always possible to recover $P$ from $F(x)$? If no, then your question also has no as an answer.

This might be related to Minkovski sums of polytopes.

Improve this answer
$\endgroup$
1
$\begingroup$

Check out this quite recent paper of Dokmanic et al (arxiv 1502.07541v2)

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is not directly related since in the Euclidian distance matrix you know already the map $k \rightarrow (i,j)$. $\endgroup$
    – Raphael J.F. Berger
    Commented Dec 15, 2015 at 15:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .