Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

I am attempting to resolve a problem of inferring Cartesian position from distance. I have a set of nodes arbitrarily but statically positioned on a 2-D plane. Every node is aware of its position relative to the other $n-1$ nodes. From this set of $n$ nodes, is it possible to infer each node's position ($x$,$y$) by choosing any node and using it as a basis?

For example, with two nodes, this is not possible, as the distance alone leaves open the possibility of the node not chosen as the basis for being located anywhere in the radial distance from the basis node.

With three nodes, it also seems impossible because the orientation can be flipped and is thus ambiguous based solely on distance. How many nodes are needed to unambiguously infer the position of the elements on a Cartesian plane?

share|improve this question
I am not very clear about your problem. You have $n$ nodes, one of them is fixed. You can rotate the $n$ nodes around the fixed node, so no matter how many nodes you have, it is impossible. – Peng Zhang Feb 7 '12 at 16:39
I can rotate them, yes, but I hope to obtain a coordinate system derived from these distances. I can rotate them and have the coordinates be at the new location but each inter-coordinate distance will remain the same. Is there some way to determine the layout of these coordinate unambiguously? If so, how many nodes are needed to accomplish this? – Mat Feb 7 '12 at 17:21
You can't ever do this completely unambiguously. If all you have is distances, you can always reflect across some axis or rotate the set of points or translate them and the distances won't change. -- If you want uniqueness mod rigid transformations like this, then all you need is three points in general position. Then I think you can triangulate all the others. – John Moeller Feb 7 '12 at 19:23
@Mat Oh, by the way, what's your research interest in this question? It would be nice if you would edit your question to reflect that. – John Moeller Feb 7 '12 at 19:25
Adding to what @JohnMoeller said - given 3 points, you can easily deduce that they are in general position from the distances: the triangle inequality will be sharp. – Shir Feb 8 '12 at 7:03
show 2 more comments

1 Answer

up vote 2 down vote accepted

I think that "Trilateration" should solve your problem.

In geometry, trilateration is the process of determinating absolute or relative locations of points by measurement of distances, using the geometry of circles, spheres or triangles. In addition to its interest as a geometric problem, trilateration does have practical applications in surveying and navigation, including global positioning systems (GPS). In contrast to triangulation it does not involve the measurement of angles. ...

share|improve this answer
Interesting. Thank you for putting a name for the process. I will investigate this term further for application toward my problem. – Mat Feb 8 '12 at 15:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.