Positioning Devices (Intersecting Circles)

Question

I have a series of points, which represent mobile devices within a room. Previously I have systematically emitted a ping from each and recorded the time at which it arrives at the others to calculate the distances.

Here's a simple diagram of an example network.

The bottom A node should have been a D instead

After recording the distances I have the distance information in hashes.

A = {B: 2, C: 1, D: 3}
B = {A: 2, C: 2, D: 2}
C = {A: 1, B: 2, D: 2}
D = {A: 3, B: 2, C: 2}

My maths is rusty, but I feel like I should be able to then draw circles using these values as the respective and then intersect the circles to calculate a relative graph of the nodes.

Every time I try to do it I start out with a series of circles drawn around the root node (in this case A) that looks something like this:

I know that the other nodes must lie on the lines that I have drawn around A, but without being able to position them, how do you draw their distances so that you may intersect the circles and create the graph?

Answer 1

Start with any one point say A. Now take the second point say B, and plot it somewhere on the circle with the center at A and radius as distance between A and B. Now take another point C. Let the distance (A,C)=x and (B,C)=y. Find the point of intersection of the circles (A,x) and (B,y). Mark it as C.

where circle (P,q) specifies center at P and radius q.

If no such point exists, then the given data is incorrect.

Now take the 4^th point and similarly find the point of intersection of circles with centers at first three points and radii as distance between 4th and other three points respectively. Apply this method until all the points are plotted.

Note that there can be infinitely many solutions as RobH pointed out. Since you need only a virtual representation, I guess anyone of the valid solutions suffices.

The above algorithm has an order of O(N^2). It may be inefficient if the number of points are greater than 10000.

Also note that, to find the point of intersection of k circles, you first need to find the point of intersection for any two circles and validate these points on the remaining circles. This is because k circles can at most intersect at two points, assuming all have distinct centers.

EDIT: At any stage if there are two valid plots for a point, we can choose anyone of them and yet we arrive at one of the valid solutions.