Given the edge lengths of a straight-edge framework (a graph embedded in space), how can we reconstruct the positions of the vertices? This problem, which arises all the time in practical applications, can be surprisingly difficult. There is an efficient algorithm based on semi-definite programming in case the framework is \emph{universally}
rigid: Up to congruence, there is only one embedding (in any
dimension) with the given edge lengths. Generic universally rigid frameworks can be characterized by the existence of a positive semi-definite stress matrix. The proof of this fact relies on an analysis of the convex set of possible edge-length measurements, and a new sufficient condition for strict complementarity in semi-definite programming.
This is joint work with Steven Gortler.
Copyright. All Rights Reserved.