Given a graph together with positive weights associated to its edges, the “2D Localization” problem asks for a placement of the graph vertices in the plane such that the edge lengths match the given weights. A slightly easier case — the “single unknown distance” problem — asks only for the possible values of one unknown distance between a pair of vertices. Both problems can be easily formulated algebraically and could, in principle, be addressed with variations of the doubly-exponential time Groebner Basis algorithm. But of course this is not feasible in practice, even for small cases.
Known results from rigidity theory, together with techniques involving algebraic matroids, a theorem of Lovasz and Dress and the formulation of the problem in terms of Cayley (rather than Cartesian) coordinates, help reduce the single-distance problem to the computation of a so-called circuit polynomial in the Cayley-Menger ideal.
By taking into account combinatorial rigidity properties of the underlying graphs, we develop a new algorithm that significantly outperforms Groebner Bases for computing such polynomials. We introduce a new operation on graphs called a “combinatorial resultant,” which captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity-circuit graph has a “construction tree,” with this operation marking the tree's interior nodes and with K4 graphs at the leaves. Our algorithm performs an algebraic elimination (using classical resultants) guided by the construction tree. A number of intriguing open questions remain — both combinatorial and algebraic.
To demonstrate the effectiveness of our new method, we implemented it in Mathematica: it took less than 15 seconds on an example where a Groebner Basis calculation took 5 days and 6 hrs.
This is joint work with Goran Malic.