Search Results

Documents authored by Maria, Clément

Document
DOI: 10.4230/LIPIcs.ESA.2022.78
Localized Geometric Moves to Compute Hyperbolic Structures on Triangulated 3-Manifolds

Authors: Clément Maria and Owen Rouillé

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
A fundamental way to study 3-manifolds is through the geometric lens, one of the most prominent geometries being the hyperbolic one. We focus on the computation of a complete hyperbolic structure on a connected orientable hyperbolic 3-manifold with torus boundaries. This family of 3-manifolds includes the knot complements. This computation of a hyperbolic structure requires the resolution of gluing equations on a triangulation of the space, but not all triangulations admit a solution to the equations. In this paper, we propose a new method to find a triangulation that admits a solution to the gluing equations, using convex optimization and localized combinatorial modifications. It is based on Casson and Rivin’s reformulation of the equations. We provide a novel approach to modify a triangulation and update its geometry, along with experimental results to support the new method.
Cite as

Clément Maria and Owen Rouillé. Localized Geometric Moves to Compute Hyperbolic Structures on Triangulated 3-Manifolds. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 78:1-78:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{maria_et_al:LIPIcs.ESA.2022.78,
  author =	{Maria, Cl\'{e}ment and Rouill\'{e}, Owen},
  title =	{{Localized Geometric Moves to Compute Hyperbolic Structures on Triangulated 3-Manifolds}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{78:1--78:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.78},
  URN =		{urn:nbn:de:0030-drops-170168},
  doi =		{10.4230/LIPIcs.ESA.2022.78},
  annote =	{Keywords: knots and 3-manifolds, triangulation, hyperbolic structure, Thurston equations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.53
Parameterized Complexity of Quantum Knot Invariants

Authors: Clément Maria

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

Abstract
We give a general fixed parameter tractable algorithm to compute quantum invariants of links presented by planar diagrams, whose complexity is singly exponential in the carving-width (or the tree-width) of the diagram. In particular, we get a O(N^{3/2 cw} poly(n)) ∈ N^O(√n) time algorithm to compute any Reshetikhin-Turaev invariant - derived from a simple Lie algebra 𝔤 - of a link presented by a planar diagram with n crossings and carving-width cw, and whose components are coloured with 𝔤-modules of dimension at most N. For example, this includes the N^{th}-coloured Jones polynomial.
Cite as

Clément Maria. Parameterized Complexity of Quantum Knot Invariants. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{maria:LIPIcs.SoCG.2021.53,
  author =	{Maria, Cl\'{e}ment},
  title =	{{Parameterized Complexity of Quantum Knot Invariants}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{53:1--53:17},
  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/entities/document/10.4230/LIPIcs.SoCG.2021.53},
  URN =		{urn:nbn:de:0030-drops-138527},
  doi =		{10.4230/LIPIcs.SoCG.2021.53},
  annote =	{Keywords: computational knot theory, parameterized complexity, quantum invariants}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.56
Intrinsic Topological Transforms via the Distance Kernel Embedding

Authors: Clément Maria, Steve Oudot, and Elchanan Solomon

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Topological transforms are parametrized families of topological invariants, which, by analogy with transforms in signal processing, are much more discriminative than single measurements. The first two topological transforms to be defined were the Persistent Homology Transform (PHT) and Euler Characteristic Transform (ECT), both of which apply to shapes embedded in Euclidean space. The contribution of this paper is to define topological transforms for abstract metric measure spaces. Our proposed pipeline is to pre-compose the PHT or ECT with a Euclidean embedding derived from the eigenfunctions and eigenvalues of an integral operator. To that end, we define and study an integral operator called the distance kernel operator, and demonstrate that it gives rise to stable and quasi-injective topological transforms. We conclude with some numerical experiments, wherein we compute and compare the eigenfunctions and eigenvalues of our operator across a range of standard 2- and 3-manifolds.
Cite as

Clément Maria, Steve Oudot, and Elchanan Solomon. Intrinsic Topological Transforms via the Distance Kernel Embedding. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{maria_et_al:LIPIcs.SoCG.2020.56,
  author =	{Maria, Cl\'{e}ment and Oudot, Steve and Solomon, Elchanan},
  title =	{{Intrinsic Topological Transforms via the Distance Kernel Embedding}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{56:1--56:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.56},
  URN =		{urn:nbn:de:0030-drops-122145},
  doi =		{10.4230/LIPIcs.SoCG.2020.56},
  annote =	{Keywords: Topological Transforms, Persistent Homology, Inverse Problems, Spectral Geometry, Algebraic Topology, Topological Data Analysis}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.64
Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants

Authors: Clément Maria and Jonathan Spreer

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Turaev-Viro invariants are amongst the most powerful tools to distinguish 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them rely on the enumeration of an extremely large set of combinatorial data defined on the triangulation, regardless of the underlying topology of the manifold. In the article, we propose a finer study of these combinatorial data, called admissible colourings, in relation with the cohomology of the manifold. We prove that the set of admissible colourings to be considered is substantially smaller than previously known, by furnishing new upper bounds on its size that are aware of the topology of the manifold. Moreover, we deduce new topology-sensitive enumeration algorithms based on these bounds. The paper provides a theoretical analysis, as well as a detailed experimental study of the approach. We give strong experimental evidence on large manifold censuses that our upper bounds are tighter than the previously known ones, and that our algorithms outperform significantly state of the art implementations to compute Turaev-Viro invariants.
Cite as

Clément Maria and Jonathan Spreer. Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{maria_et_al:LIPIcs.ESA.2016.64,
  author =	{Maria, Cl\'{e}ment and Spreer, Jonathan},
  title =	{{Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.64},
  URN =		{urn:nbn:de:0030-drops-64050},
  doi =		{10.4230/LIPIcs.ESA.2016.64},
  annote =	{Keywords: low-dimensional topology, triangulations of 3-manifolds, cohomology theory, Turaev-Viro invariants, combinatorial algorithms}
}
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