Document

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

A Reeb graph is a graphical representation of a scalar function on a topological space that encodes the topology of the level sets. A Reeb space is a generalization of the Reeb graph to a multiparameter function. In this paper, we propose novel constructions of Reeb graphs and Reeb spaces that incorporate the use of a measure. Specifically, we introduce measure-theoretic Reeb graphs and Reeb spaces when the domain or the range is modeled as a metric measure space (i.e., a metric space equipped with a measure). Our main goal is to enhance the robustness of the Reeb graph and Reeb space in representing the topological features of a scalar field while accounting for the distribution of the measure. We first introduce a Reeb graph with local smoothing and prove its stability with respect to the interleaving distance. We then prove the stability of a Reeb graph of a metric measure space with respect to the measure, defined using the distance to a measure or the kernel distance to a measure, respectively.

Qingsong Wang, Guanqun Ma, Raghavendra Sridharamurthy, and Bei Wang. Measure-Theoretic Reeb Graphs and Reeb Spaces. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 80:1-80:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.SoCG.2024.80, author = {Wang, Qingsong and Ma, Guanqun and Sridharamurthy, Raghavendra and Wang, Bei}, title = {{Measure-Theoretic Reeb Graphs and Reeb Spaces}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {80:1--80:18}, 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.80}, URN = {urn:nbn:de:0030-drops-200257}, doi = {10.4230/LIPIcs.SoCG.2024.80}, annote = {Keywords: Reeb graph, Reeb space, metric measure space, topological data analysis} }

Document

**Published in:** Dagstuhl Reports, Volume 13, Issue 5 (2023)

This report documents the program and the outcomes of Dagstuhl Seminar 23192 "Topological Data Analysis and Applications". The seminar brought together researchers with backgrounds in mathematics, computer science, and different application domains with the aim of identifying and exploring emerging directions within computational topology for data analysis. This seminar was designed to be a followup event to two successful Dagstuhl Seminars (17292, July 2017; 19212, May 2019). The list of topics and participants were updated to reflect recent developments and to engage wider participation. Close interaction between the participants during the seminar accelerated the convergence between mathematical and computational thinking in the development of theories and scalable algorithms for data analysis, and the identification of different applications of topological analysis.

Ulrich Bauer, Vijay Natarajan, and Bei Wang. Topological Data Analysis and Applications (Dagstuhl Seminar 23192). In Dagstuhl Reports, Volume 13, Issue 5, pp. 71-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{bauer_et_al:DagRep.13.5.71, author = {Bauer, Ulrich and Natarajan, Vijay and Wang, Bei}, title = {{Topological Data Analysis and Applications (Dagstuhl Seminar 23192)}}, pages = {71--95}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {13}, number = {5}, editor = {Bauer, Ulrich and Natarajan, Vijay and Wang, Bei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.5.71}, URN = {urn:nbn:de:0030-drops-193652}, doi = {10.4230/DagRep.13.5.71}, annote = {Keywords: algorithms, applications, computational topology, topological data analysis, visualization} }

Document

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

We first introduce the notion of meta-rank for a 2-parameter persistence module, an invariant that captures the information behind images of morphisms between 1D slices of the module. We then define the meta-diagram of a 2-parameter persistence module to be the Möbius inversion of the meta-rank, resulting in a function that takes values from signed 1-parameter persistence modules. We show that the meta-rank and meta-diagram contain information equivalent to the rank invariant and the signed barcode. This equivalence leads to computational benefits, as we introduce an algorithm for computing the meta-rank and meta-diagram of a 2-parameter module M indexed by a bifiltration of n simplices in O(n³) time. This implies an improvement upon the existing algorithm for computing the signed barcode, which has O(n⁴) time complexity. This also allows us to improve the existing upper bound on the number of rectangles in the rank decomposition of M from O(n⁴) to O(n³). In addition, we define notions of erosion distance between meta-ranks and between meta-diagrams, and show that under these distances, meta-ranks and meta-diagrams are stable with respect to the interleaving distance. Lastly, the meta-diagram can be visualized in an intuitive fashion as a persistence diagram of diagrams, which generalizes the well-understood persistence diagram in the 1-parameter setting.

Nate Clause, Tamal K. Dey, Facundo Mémoli, and Bei Wang. Meta-Diagrams for 2-Parameter Persistence. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{clause_et_al:LIPIcs.SoCG.2023.25, author = {Clause, Nate and Dey, Tamal K. and M\'{e}moli, Facundo and Wang, Bei}, title = {{Meta-Diagrams for 2-Parameter Persistence}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {25:1--25: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.25}, URN = {urn:nbn:de:0030-drops-178754}, doi = {10.4230/LIPIcs.SoCG.2023.25}, annote = {Keywords: Multiparameter persistence modules, persistent homology, M\"{o}bius inversion, barcodes, computational topology, topological data analysis} }

Document

Media Exposition

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

Discrete stratified Morse theory, first introduced by Knudson and Wang, works toward a discrete analogue of Goresky and MacPherson’s stratified Morse theory. It is inspired by the works of Forman on discrete Morse theory by generalizing stratified Morse theory to finite simplicial complexes. The class of discrete stratified Morse functions is much larger than that of discrete Morse functions. Any arbitrary real-valued function defined on a finite simplicial complex can be made into a discrete stratified Morse function with the proper stratification of the underlying complex. An algorithm is given by Knudson and Wang that constructs a discrete stratified Morse function on any finite simplicial complex equipped with an arbitrary real-valued function. Our media contribution is an open-sourced visualization tool that implements such an algorithm for 2-complexes embedded in the plane, and provides an interactive demo for users to explore the algorithmic process and to perform homotopy-preserving simplification of the resulting stratified complex.

Youjia Zhou, Kevin Knudson, and Bei Wang. Visual Demo of Discrete Stratified Morse Theory (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 82:1-82:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{zhou_et_al:LIPIcs.SoCG.2020.82, author = {Zhou, Youjia and Knudson, Kevin and Wang, Bei}, title = {{Visual Demo of Discrete Stratified Morse Theory}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {82:1--82:4}, 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.82}, URN = {urn:nbn:de:0030-drops-122409}, doi = {10.4230/LIPIcs.SoCG.2020.82}, annote = {Keywords: Discrete Morse theory, stratified Morse theory, discrete stratified Morse theory, topological data analysis, data visualization} }

Document

**Published in:** Dagstuhl Reports, Volume 9, Issue 5 (2019)

This report documents the program and the outcomes of Dagstuhl Seminar 19212 "Topology, Computation and Data Analysis". The seminar brought together researchers with mathematical and computational backgrounds in addressing emerging directions within computational topology for data analysis in practice. This seminar was designed to be a followup event after a very successful Dagstuhl Seminar (17292; July 2017). The list of topics and participants were updated to keep the discussions diverse, refreshing, and engaging. This seminar facilitated close interactions among the attendees with the aim of accelerating the convergence between mathematical and computational thinking in the development of theories and scalable algorithms for data analysis.

Michael Kerber, Vijay Natarajan, and Bei Wang. Topology, Computation and Data Analysis (Dagstuhl Seminar 19212). In Dagstuhl Reports, Volume 9, Issue 5, pp. 110-131, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{kerber_et_al:DagRep.9.5.110, author = {Kerber, Michael and Natarajan, Vijay and Wang, Bei}, title = {{Topology, Computation and Data Analysis (Dagstuhl Seminar 19212)}}, pages = {110--131}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {5}, editor = {Kerber, Michael and Natarajan, Vijay and Wang, Bei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.5.110}, URN = {urn:nbn:de:0030-drops-113832}, doi = {10.4230/DagRep.9.5.110}, annote = {Keywords: computational topology, topological data analysis, Topology based visualization} }

Document

**Published in:** LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

We study Vietoris-Rips and Cech complexes of metric wedge sums and metric gluings. We show that the Vietoris-Rips (resp. Cech) complex of a wedge sum, equipped with a natural metric, is homotopy equivalent to the wedge sum of the Vietoris-Rips (resp. Cech) complexes. We also provide generalizations for certain metric gluings, i.e. when two metric spaces are glued together along a common isometric subset. As our main example, we deduce the homotopy type of the Vietoris-Rips complex of two metric graphs glued together along a sufficiently short path. As a result, we can describe the persistent homology, in all homological dimensions, of the Vietoris-Rips complexes of a wide class of metric graphs.

Michal Adamaszek, Henry Adams, Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic, Bei Wang, Yusu Wang, and Lori Ziegelmeier. Vietoris-Rips and Cech Complexes of Metric Gluings. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{adamaszek_et_al:LIPIcs.SoCG.2018.3, author = {Adamaszek, Michal and Adams, Henry and Gasparovic, Ellen and Gommel, Maria and Purvine, Emilie and Sazdanovic, Radmila and Wang, Bei and Wang, Yusu and Ziegelmeier, Lori}, title = {{Vietoris-Rips and Cech Complexes of Metric Gluings}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.3}, URN = {urn:nbn:de:0030-drops-87162}, doi = {10.4230/LIPIcs.SoCG.2018.3}, annote = {Keywords: Vietoris-Rips and Cech complexes, metric space gluings and wedge sums, metric graphs, persistent homology} }

Document

**Published in:** LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

In this paper, we investigate a sheaf-theoretic interpretation of stratification learning. Motivated by the work of Alexandroff (1937) and McCord (1978), we aim to redirect efforts in the computational topology of triangulated compact polyhedra to the much more computable realm of sheaves on partially ordered sets. Our main result is the construction of stratification learning algorithms framed in terms of a sheaf on a partially ordered set with the Alexandroff topology. We prove that the resulting decomposition is the unique minimal stratification for which the strata are homogeneous and the given sheaf is constructible. In particular, when we choose to work with the local homology sheaf, our algorithm gives an alternative to the local homology transfer algorithm given in Bendich et al. (2012), and the cohomology stratification algorithm given in Nanda (2017). We envision that our sheaf-theoretic algorithm could give rise to a larger class of stratification beyond homology-based stratification. This approach also points toward future applications of sheaf theory in the study of topological data analysis by illustrating the utility of the language of sheaf theory in generalizing existing algorithms.

Adam Brown and Bei Wang. Sheaf-Theoretic Stratification Learning. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{brown_et_al:LIPIcs.SoCG.2018.14, author = {Brown, Adam and Wang, Bei}, title = {{Sheaf-Theoretic Stratification Learning}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {14:1--14:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.14}, URN = {urn:nbn:de:0030-drops-87270}, doi = {10.4230/LIPIcs.SoCG.2018.14}, annote = {Keywords: Sheaf theory, stratification learning, topological data analysis, stratification} }

Document

**Published in:** LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Inspired by the works of Forman on discrete Morse theory, which is a combinatorial adaptation to cell complexes of classical Morse theory on manifolds, we introduce a discrete analogue of the stratified Morse theory of Goresky and MacPherson. We describe the basics of this theory and prove fundamental theorems relating the topology of a general simplicial complex with the critical simplices of a discrete stratified Morse function on the complex. We also provide an algorithm that constructs a discrete stratified Morse function out of an arbitrary function defined on a finite simplicial complex; this is different from simply constructing a discrete Morse function on such a complex. We borrow Forman's idea of a "user's guide," where we give simple examples to convey the utility of our theory.

Kevin Knudson and Bei Wang. Discrete Stratified Morse Theory: A User's Guide. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{knudson_et_al:LIPIcs.SoCG.2018.54, author = {Knudson, Kevin and Wang, Bei}, title = {{Discrete Stratified Morse Theory: A User's Guide}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {54:1--54:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.54}, URN = {urn:nbn:de:0030-drops-87671}, doi = {10.4230/LIPIcs.SoCG.2018.54}, annote = {Keywords: Discrete Morse theory, stratified Morse theory, topological data analysis} }

Document

**Published in:** Dagstuhl Reports, Volume 7, Issue 7 (2018)

This report documents the program and the outcomes of Dagstuhl Seminar 17292 "Topology, Computation and Data Analysis".
This seminar was the first of its kind in bringing together researchers with mathematical and computational backgrounds in addressing emerging directions within computational topology for data analysis in practice. The seminar connected pure and applied mathematicians, with theoretical and applied computer scientists with an interest in computational topology. It helped to facilitate interactions among data theorist and data practitioners from several communities to address challenges in computational topology, topological data analysis, and topological visualization.

Hamish Carr, Michael Kerber, and Bei Wang. Topology, Computation and Data Analysis (Dagstuhl Seminar 17292). In Dagstuhl Reports, Volume 7, Issue 7, pp. 88-109, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{carr_et_al:DagRep.7.7.88, author = {Carr, Hamish and Kerber, Michael and Wang, Bei}, title = {{Topology, Computation and Data Analysis (Dagstuhl Seminar 17292)}}, pages = {88--109}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2018}, volume = {7}, number = {7}, editor = {Carr, Hamish and Kerber, Michael and Wang, Bei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.7.88}, URN = {urn:nbn:de:0030-drops-84258}, doi = {10.4230/DagRep.7.7.88}, annote = {Keywords: computational topology, topological data analysis, Topological data visualization} }

Document

**Published in:** LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

The Reeb space, which generalizes the notion of a Reeb graph, is one of the few tools in topological data analysis and visualization suitable for the study of multivariate scientific datasets. First introduced by Edelsbrunner et al., it compresses the components of the level sets of a multivariate mapping and obtains a summary representation of their relationships. A related construction called mapper, and a special case of the mapper construction called the Joint Contour Net have been shown to be effective in visual analytics. Mapper and JCN are intuitively regarded as discrete approximations of the Reeb space, however without formal proofs or approximation guarantees. An open question has been proposed by Dey et al. as to whether the mapper construction converges to the Reeb space in the limit.
In this paper, we are interested in developing the theoretical understanding of the relationship between the Reeb space and its discrete approximations to support its use in practical data analysis. Using tools from category theory, we formally prove the convergence between the Reeb space and mapper in terms of an interleaving distance between their categorical representations. Given a sequence of refined discretizations, we prove that these approximations converge to the Reeb space in the interleaving distance; this also helps to quantify the approximation quality of the discretization at a fixed resolution.

Elizabeth Munch and Bei Wang. Convergence between Categorical Representations of Reeb Space and Mapper. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{munch_et_al:LIPIcs.SoCG.2016.53, author = {Munch, Elizabeth and Wang, Bei}, title = {{Convergence between Categorical Representations of Reeb Space and Mapper}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {53:1--53:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.53}, URN = {urn:nbn:de:0030-drops-59454}, doi = {10.4230/LIPIcs.SoCG.2016.53}, annote = {Keywords: Topological data analysis, Reeb space, mapper, category theory} }

Document

**Published in:** LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

We show that geometric inference of a point cloud can be calculated by examining its kernel density estimate with a Gaussian kernel. This allows one to consider kernel density estimates, which are robust to spatial noise, subsampling, and approximate computation in comparison to raw point sets. This is achieved by examining the sublevel sets of the kernel distance, which isomorphically map to superlevel sets of the kernel density estimate. We prove new properties about the kernel distance, demonstrating stability results and allowing it to inherit reconstruction results from recent advances in distance-based topological reconstruction. Moreover, we provide an algorithm to estimate its topology using weighted Vietoris-Rips complexes.

Jeff M. Phillips, Bei Wang, and Yan Zheng. Geometric Inference on Kernel Density Estimates. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 857-871, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{phillips_et_al:LIPIcs.SOCG.2015.857, author = {Phillips, Jeff M. and Wang, Bei and Zheng, Yan}, title = {{Geometric Inference on Kernel Density Estimates}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {857--871}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.857}, URN = {urn:nbn:de:0030-drops-51349}, doi = {10.4230/LIPIcs.SOCG.2015.857}, annote = {Keywords: topological data analysis, kernel density estimate, kernel distance} }