Abstract :

It is a trivial matter to see that given the coordinates of n points in R^k, the distance between any two points can be computed efficiently. However, the inverse problem --- given a subset of interpoint distances, find the coordinates of points (called a realization) in R^k (where k>=1 is fixed) that fit those distances --- turns out to be anything but trivial. In fact, this problem has been shown to be NP-hard for any fixed k>=1. On the other hand, this problem arises from many applications, e.g., surveying, satellite ranging, sensor network localization and molecular conformation, just to name a few. Thus, many heuristics have been proposed. However, they either do not have any theoretical guarantees, or they work only for some very restricted classes of instances.

Recently, Biswas and Ye (2004) have proposed a semidefinite programming (SDP) based model for the problem and have reported its superb experimental performance. Our work is motivated by the desire to explain this phenomenon in a rigorous manner. We show that the SDP model can be used to find a realization in the required dimension if the input instance satisfies certain uniqueness property. This uniqueness property has a straightforward geometric interpretation, and it allows us to identify a large class of efficiently realizable instances. Furthermore, it allows us to make some interesting connections with various notions in the rigidity theory of graphs. We then show how ideas from the theory of tensegrities can be used to enhance the SDP model, which in turn allows us to design efficient heuristics for the Graph Realization Problem.