1 Search Results for "Malić, Goran"

Document
DOI: 10.4230/LIPIcs.SoCG.2021.52
Combinatorial Resultants in the Algebraic Rigidity Matroid

Authors: Goran Malić and Ileana Streinu

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

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.
Cite as

Goran Malić and Ileana Streinu. Combinatorial Resultants in the Algebraic Rigidity Matroid. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 52:1-52:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.52},
  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}
}
  • Refine by Author
  • 1 Malić, Goran
  • 1 Streinu, Ileana

  • Refine by Classification
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Computing methodologies → Combinatorial algorithms
  • 1 General and reference → Experimentation
  • 1 General and reference → Performance
  • 1 Mathematics of computing → Mathematical software performance
  • Show More...

  • Refine by Keyword
  • 1 Cayley-Menger ideal
  • 1 Gröbner basis elimination
  • 1 circuit polynomial
  • 1 combinatorial resultant
  • 1 inductive construction
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact