License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.52
URN: urn:nbn:de:0030-drops-138514
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13851/
Go to the corresponding LIPIcs Volume Portal

Malić, Goran ; Streinu, Ileana

Combinatorial Resultants in the Algebraic Rigidity Matroid

pdf-format:
LIPIcs-SoCG-2021-52.pdf (0.9 MB)

Abstract

Motivated by a rigidity-theoretic perspective on the Localization Problem in 2D, we develop an algorithm for computing circuit polynomials in the algebraic rigidity matroid CM_n associated to the Cayley-Menger ideal for n points in 2D. We introduce combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity circuit has a construction tree from K₄ graphs based on this operation. Our algorithm performs an algebraic elimination guided by the construction tree, and uses classical resultants, factorization and ideal membership. To demonstrate its effectiveness, we implemented our algorithm in Mathematica: it took less than 15 seconds on an example where a Gröbner Basis calculation took 5 days and 6 hrs.

BibTeX - Entry

@InProceedings{malic_et_al:LIPIcs.SoCG.2021.52,
  author =	{Mali\'{c}, Goran and Streinu, Ileana},
  title =	{{Combinatorial Resultants in the Algebraic Rigidity Matroid}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{52:1--52:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13851},
  URN =		{urn:nbn:de:0030-drops-138514},
  doi =		{10.4230/LIPIcs.SoCG.2021.52},
  annote =	{Keywords: Cayley-Menger ideal, rigidity matroid, circuit polynomial, combinatorial resultant, inductive construction, Gr\"{o}bner basis elimination}
}

Keywords: Cayley-Menger ideal, rigidity matroid, circuit polynomial, combinatorial resultant, inductive construction, Gröbner basis elimination
Collection: 37th International Symposium on Computational Geometry (SoCG 2021)
Issue Date: 2021
Date of publication: 02.06.2021
Supplementary Material: Polynomials computed by our algorithm are made available in Mathematica’s compressed and portable wdx format at the following GitHub repository:
Dataset: https://github.com/circuitPolys/CayleyMenger

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI