Define positions of a set of points given (only) the distances between them

Question

I have been thinking about spatial transforms.

Given $n$ points, there are $\frac{n!}{(n-2)!2!}$ combinations of selecting two points, so for 64 points in space, there are 2016 single point-to-point relationships (e.g. distances between points involved).

Can a set of points be uniquely defined by the corresponding full set of relationships. That is to say, if I had points A,B and C, could I derive a unique point arrangements to satisfy a list of distances, AB, AC, BC. Could I do this generally for any list of point to point distances given $n$ points? How is it done?

I understand that given only relative position, placement of the points in an absolute coordinate system is impossible. I understand also, that with few points, e.g. 2,3.., the solution is not unique - but what about larger numbers?

Edit - Addition of a physical constraint.

Let us define a 16 by 16 by 16 grid $G$, based on the Cartesian coordinate system. Let us calculate/define a set of distances $D_R$, that represent the physical distance between points in $G$. If we have a nice continuous function without a singularity - to represent gradient in the space for example - then we could correct our distance $D_R$, to some effective distance $D_E$, by multiply each distance by the appropriate mean gradient for example. The task is to define the points in some "Effective Distance Space". My point is that in physical reality there are constraints on the sets of distances - I don't expect to find a solution to an arbitrary set of distances. Does this change things?

This post imported from StackExchange Mathematics at 2014-06-16 11:28 (UCT), posted by SE-user Andrewb

Comments

The full set of difference vecotrs $\mathbf{r}_{i,j} = \mathbf{r}_i - \mathbf{r}_j$ is sometimes treated as a formal constraint in defining what is meant by a "rigid body" in contexts like rotations of rigid bodies. I believe that Goldstein does that at some point. But in this case the dimension of the vectors sets the dimension of the problem, so the issues that Emilio discusses never come up.

This post imported from StackExchange Mathematics at 2014-06-16 11:28 (UCT), posted by SE-user dmckee

---

Re: your edit, it's not exactly clear what you mean. If you mean you have a set of points $\{p_k\}$ and a smooth function $f$, and you want to move each point by a multiple of the gradient, i.e. $p_k\mapsto p_k+h\nabla f(p_k)$, then there you have your answer. It's not clear what you mean by "multiply each distance by the appropriate mean gradient", but it sounds awfully like equating a vector to a scalar. If you provide more specific details about what you mean then I'll address that.

This post imported from StackExchange Mathematics at 2014-06-16 11:28 (UCT), posted by SE-user episanty

---

@episanty - You raise a good point - I'm sorry for the lack of clarity. I think most likely the function returns a scalar - e.g. the time taken to travel the distance between two points given the gradients which exist between the two points (this was the analogy I was going for anyway). this appears to change the problem somewhat, as we suffer information loss in considering a list of scalars over a list of vectors... I shall give some thought as to whether or not the context lends itself to your vector approach.

This post imported from StackExchange Mathematics at 2014-06-16 11:28 (UCT), posted by SE-user Andrewb

---

@Andrewb If you provide a clear description of how you get from your initial distances to the new ones, then it will be easier to see. Be aware, though, that even with small perturbations if you do not have some specific geometric constraints in general the minimal dimension will still be $n-1$, because the determinant of the relevant matrix is a continuous function, and its zeros have measure zero. Nevertheless, the $(n-1)$-volume will be very small, though.

This post imported from StackExchange Mathematics at 2014-06-16 11:28 (UCT), posted by SE-user episanty

Answer 1

This is in general not possible.

First of all, whatever solution you get will not be unique, as you indicate, in the sense that global translations and rotations of the set of points will also be a solution to the problem. Beyond that, there are two possible pitfalls:

• The set of "distances" can be inconsistent if set wrong. At the very least it must obey all triangle inequalities of the form $d_{AB}+d_{BC}\leq d_{AC}$; if it doesn't then there is no chance of a realization.
• It can also not be realizable in three dimensions. The simplest example of this is five equidistant points. Four points you can fit on the vertices of a tetrahedron, but to fit a fifth point you need a four-dimensional simplex to have the embedding you want. This will generally be the case: a consistent set of distances between $n$ points can be realized in $n-1$ dimensions, but there's no guarantee of lower-dimensional realizations.

In general, this is how it goes if you're given a set of such distances between $n$ points.

• You first check that they're consistent. If they're not, then you can give up right away.#

• If they are, then you start working in $n-1$ dimensions. You position your first point wherever. You choose your second point anywhere on the $(n-2)$-dimensional hypersphere that's the right distance $d_{12}$ away. The third point needs to be $d_{13}$ away from the first one and $d_{23}$ away from the second one, so it will lie on the $(n-3)$-dimensional intersection of two $(n-2)$-dimensional hyperspheres. This is keeps going: the $k$th point will be under $k-1$ constraints and can therefore lie anywhere in an $(n-1)-(k-1)=(n-k)$-dimensional hypersurface. By the end, your second-to-last point will lie in a circle, and the last point will be completely determined.

  Note also that you're guaranteed these intersections will not vanish whenever your system of distances is consistent.

• You then have a set of $n$ points $p_k$ in $n-1$ dimensions, but you do not know whether there exists some lower-dimensional slice of that space that will still fit the points. For example, the distances $d_{jk} = |j-k|$ will fit in a one-dimensional slice. Your task, then, is to find the lowest-dimensional subspace that will fit your points.

  The answer to this question can be found by considering the set of separation vectors, $\{v_k=p_k-p_1:2\leq k\leq n\}$. The dimension of their span is equal to the rank of the $(n-1)$-dimensional square matrix of their entries. It is then a task in standard linear algebra to choose a basis from these vectors, and to express the rest in terms of them. That will give you the 'tightest' fit possible. Whether that's in three dimensions or more, though, will depend on your set of distances.

This post imported from StackExchange Mathematics at 2014-06-16 11:28 (UCT), posted by SE-user episanty

Answer 2

The set of distances between points defines their position up to rotation, translation and reflection. The proof is simple--- choose one point to be at the origin, place the next point along the x-axis, the third along the x-y plane (unique up to reflection), the fourth in the x-y-z volume (unique up to reflection), and so on. At each added point, the new point is uniquely determined by the generalized side-side-side theorem, that all simplicies with identical side-length are identical.

Since there are n(n-1)/2 distances between n points, and only dn coordinates determining these, minus a fixed number less than d(d+1)/2 of parameters taken away for rotations and translations, there are constraints on the position data when n is large.

The algorithm above will give you all the constraints: it will tell you if the distances are consistent, the constraints first pop up when you have points which are linearly dependent on previous points, which generically happens when you have d+1 points in d dimensions.

The idea of relational distances determining the geometry is explored in the mathematics and physics literature under "relational geometry". This is one of the ideas which motivated loop quantum gravity.