Computing Circuit Polynomials in the Algebraic Rigidity Matroid
Goran Malić, Ileana Streinu · SIAM Journal on Applied Algebra and Geometry · 2023
Abstract. We present an algorithm for computing circuit polynomials in the algebraic rigidity matroid [Formula: see text] associated to the Cayley–Menger ideal [Formula: see text] for [Formula: see text] points in 2D. It relies on combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in this ideal. We show that every rigidity circuit has a construction tree from [Formula: see text] graphs based on this operation. Our algorithm performs an algebraic elimination guided by such a construction tree and uses classical resultants, factorization, and ideal membership. To highlight its effectiveness, we implemented the algorithm in Mathematica: it took less than 15 seconds on an example where a Gröbner basis calculation took 5 days and 6 hours. Additional speed-ups are obtained using non-[Formula: see text] generators of the Cayley–Menger ideal and simple variations on our main algorithm.