4 Search Results for "Mrozek, Marian"

Document
DOI: 10.4230/LIPIcs.SoCG.2024.15
Wrapping Cycles in Delaunay Complexes: Bridging Persistent Homology and Discrete Morse Theory

Authors: Ulrich Bauer and Fabian Roll

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We study the connection between discrete Morse theory and persistent homology in the context of shape reconstruction methods. Specifically, we consider the construction of Wrap complexes, introduced by Edelsbrunner as a subcomplex of the Delaunay complex, and the construction of lexicographic optimal homologous cycles, also considered by Cohen–Steiner, Lieutier, and Vuillamy in a similar setting. We show that for any cycle in a Delaunay complex for a given radius parameter, the lexicographically optimal homologous cycle is supported on the Wrap complex for the same parameter, thereby establishing a close connection between the two methods. We obtain this result by establishing a fundamental connection between reduction of cycles in the computation of persistent homology and gradient flows in the algebraic generalization of discrete Morse theory.
Cite as

Ulrich Bauer and Fabian Roll. Wrapping Cycles in Delaunay Complexes: Bridging Persistent Homology and Discrete Morse Theory. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SoCG.2024.15,
  author =	{Bauer, Ulrich and Roll, Fabian},
  title =	{{Wrapping Cycles in Delaunay Complexes: Bridging Persistent Homology and Discrete Morse Theory}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.15},
  URN =		{urn:nbn:de:0030-drops-199600},
  doi =		{10.4230/LIPIcs.SoCG.2024.15},
  annote =	{Keywords: persistent homology, discrete Morse theory, apparent pairs, Wrap complex, lexicographic optimal chains, shape reconstruction}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.60
Slice, Simplify and Stitch: Topology-Preserving Simplification Scheme for Massive Voxel Data

Authors: Hubert Wagner

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

Abstract
We focus on efficient computations of topological descriptors for voxel data. This type of data includes 2D greyscale images, 3D medical scans, but also higher-dimensional scalar fields arising from physical simulations. In recent years we have seen an increase in applications of topological methods for such data. However, computational issues remain an obstacle. We therefore propose a streaming scheme which simplifies large 3-dimensional voxel data - while provably retaining its persistent homology. We combine this scheme with an efficient boundary matrix reduction implementation, obtaining an end-to-end tool for persistent homology of large data. Computational experiments show its state-of-the-art performance. In particular, we are now able to robustly handle complex datasets with several billions voxels on a regular laptop. A software implementation called Cubicle is available as open-source: https://bitbucket.org/hubwag/cubicle.
Cite as

Hubert Wagner. Slice, Simplify and Stitch: Topology-Preserving Simplification Scheme for Massive Voxel Data. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{wagner:LIPIcs.SoCG.2023.60,
  author =	{Wagner, Hubert},
  title =	{{Slice, Simplify and Stitch: Topology-Preserving Simplification Scheme for Massive Voxel Data}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{60:1--60:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.60},
  URN =		{urn:nbn:de:0030-drops-179107},
  doi =		{10.4230/LIPIcs.SoCG.2023.60},
  annote =	{Keywords: Computational topology, topological data analysis, topological image analysis, persistent homology, persistence diagram, discrete Morse theory, algorithm engineering, implementation, voxel data, volume data, image data}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.35
Tracking Dynamical Features via Continuation and Persistence

Authors: Tamal K. Dey, Michał Lipiński, Marian Mrozek, and Ryan Slechta

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Multivector fields and combinatorial dynamical systems have recently become a subject of interest due to their potential for use in computational methods. In this paper, we develop a method to track an isolated invariant set - a salient feature of a combinatorial dynamical system - across a sequence of multivector fields. This goal is attained by placing the classical notion of the "continuation" of an isolated invariant set in the combinatorial setting. In particular, we give a "Tracking Protocol" that, when given a seed isolated invariant set, finds a canonical continuation of the seed across a sequence of multivector fields. In cases where it is not possible to continue, we show how to use zigzag persistence to track homological features associated with the isolated invariant sets. This construction permits viewing continuation as a special case of persistence.
Cite as

Tamal K. Dey, Michał Lipiński, Marian Mrozek, and Ryan Slechta. Tracking Dynamical Features via Continuation and Persistence. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2022.35,
  author =	{Dey, Tamal K. and Lipi\'{n}ski, Micha{\l} and Mrozek, Marian and Slechta, Ryan},
  title =	{{Tracking Dynamical Features via Continuation and Persistence}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.35},
  URN =		{urn:nbn:de:0030-drops-160439},
  doi =		{10.4230/LIPIcs.SoCG.2022.35},
  annote =	{Keywords: combinatorial dynamical systems, continuation, index pair, Conley index, persistent homology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.37
Persistence of the Conley Index in Combinatorial Dynamical Systems

Authors: Tamal K. Dey, Marian Mrozek, and Ryan Slechta

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

Abstract
A combinatorial framework for dynamical systems provides an avenue for connecting classical dynamics with data-oriented, algorithmic methods. Combinatorial vector fields introduced by Forman [R. Forman, 1998; R. Forman, 1998] and their recent generalization to multivector fields [Mrozek, 2017] have provided a starting point for building such a connection. In this work, we strengthen this relationship by placing the Conley index in the persistent homology setting. Conley indices are homological features associated with so-called isolated invariant sets, so a change in the Conley index is a response to perturbation in an underlying multivector field. We show how one can use zigzag persistence to summarize changes to the Conley index, and we develop techniques to capture such changes in the presence of noise. We conclude by developing an algorithm to "track" features in a changing multivector field.
Cite as

Tamal K. Dey, Marian Mrozek, and Ryan Slechta. Persistence of the Conley Index in Combinatorial Dynamical Systems. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2020.37,
  author =	{Dey, Tamal K. and Mrozek, Marian and Slechta, Ryan},
  title =	{{Persistence of the Conley Index in Combinatorial Dynamical Systems}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{37:1--37:17},
  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.37},
  URN =		{urn:nbn:de:0030-drops-121958},
  doi =		{10.4230/LIPIcs.SoCG.2020.37},
  annote =	{Keywords: Dynamical systems, combinatorial vector field, multivector, Conley index, persistence}
}
  • Refine by Author
  • 2 Dey, Tamal K.
  • 2 Mrozek, Marian
  • 2 Slechta, Ryan
  • 1 Bauer, Ulrich
  • 1 Lipiński, Michał
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 2 Mathematics of computing → Algebraic topology
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Geometric topology

  • Refine by Keyword
  • 3 persistent homology
  • 2 Conley index
  • 2 discrete Morse theory
  • 1 Computational topology
  • 1 Dynamical systems
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2020
  • 1 2022
  • 1 2023
  • 1 2024

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