2 Search Results for "Streinu, Ileana"

Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2023.63
Interactive 2D Periodic Graphs (Media Exposition)

Authors: Alexandra Camero and Ileana Streinu

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We present an educational web app for interactively drawing and editing 2D periodic graphs. The user defines the unit cell and the finite set of vertex and edge representatives, from which a sufficiently large fragment of the periodic graph is created for the visualization. The periodic graph can also be modified by applying several transformations, including isometries and relaxations of the unit cell. A finite representation of the infinite periodic graph can be saved in an external file as a quotient graph with Z²-marked edges. Its geometry is recorded using fractional (crystallographic) coordinates. The facial structure of non-crossing periodic graphs can be revealed by the user interactively selecting face representatives. An accompanying video demonstrates the functionality of the web application.
Cite as

Alexandra Camero and Ileana Streinu. Interactive 2D Periodic Graphs (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 63:1-63:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{camero_et_al:LIPIcs.SoCG.2023.63,
  author =	{Camero, Alexandra and Streinu, Ileana},
  title =	{{Interactive 2D Periodic Graphs}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{63:1--63:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.63},
  URN =		{urn:nbn:de:0030-drops-179131},
  doi =		{10.4230/LIPIcs.SoCG.2023.63},
  annote =	{Keywords: Periodic graphs, isometric transformations}
}
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
  • 2 Streinu, Ileana
  • 1 Camero, Alexandra
  • 1 Malić, Goran

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Computing methodologies → Combinatorial algorithms
  • 1 General and reference → Experimentation
  • 1 General and reference → Performance
  • Show More...

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

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2023

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