Search Results

Documents authored by Wang, Yusu

Document
DOI: 10.4230/DagRep.14.2.206
Applied and Combinatorial Topology (Dagstuhl Seminar 24092)

Authors: Paweł Dłotko, Dmitry Feichtner-Kozlov, Anastasios Stefanou, Yusu Wang, and Jan F Senge

Published in: Dagstuhl Reports, Volume 14, Issue 2 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 24092 "Applied and Combinatorial Topology". The last twenty years of rapid development of Topological Data Analysis (TDA) have shown the need to analyze the shape of data to better understand the data. Since an explosion of new ideas in 2000’ including those of Persistent Homology and Mapper Algorithms, the community rushed to solve detailed theoretical questions related to the existing invariants. However, topology and geometry still have much to offer to the data science community. New tools and techniques are within reach, waiting to be brought over the fence to enrich our understanding and potential to analyze data. At the same time, the fields of Discrete Morse Theory (DMT) and Combinatorial Topology (CT) are developed in parallel with no strong connection to data-intensive TDA or to other statistical pipelines (e.g. machine learning). This Dagstuhl Seminar brought together a number of experts in Discrete Morse Theory, Combinatorial Topology, Topological Data Analysis, and Statistics to (i) enhance the existing interactions between these fields on the one hand, and (ii) discuss the possibilities of adopting new invariants from algebra, geometry, and topology; in particular inspired by continuous and discrete Morse theory and combinatorial topology; to analyze and better understand the notion of shape of the data. The different talks in the seminar included both introductory talks as well as current research expositions and proved fruitful for the open problem and break-out sessions. The topics that were discussed included 1) algorithmic aspects for efficient computation as well as Morse theoretic approximations 2) topological information gain of multiparameter persistence 3) understanding the magnitude function and its relation to graph problems.
Cite as

Paweł Dłotko, Dmitry Feichtner-Kozlov, Anastasios Stefanou, Yusu Wang, and Jan F Senge. Applied and Combinatorial Topology (Dagstuhl Seminar 24092). In Dagstuhl Reports, Volume 14, Issue 2, pp. 206-239, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{dlotko_et_al:DagRep.14.2.206,
  author =	{D{\l}otko, Pawe{\l} and Feichtner-Kozlov, Dmitry and Stefanou, Anastasios and Wang, Yusu and Senge, Jan F},
  title =	{{Applied and Combinatorial Topology (Dagstuhl Seminar 24092)}},
  pages =	{206--239},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{14},
  number =	{2},
  editor =	{D{\l}otko, Pawe{\l} and Feichtner-Kozlov, Dmitry and Stefanou, Anastasios and Wang, Yusu and Senge, Jan F},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.2.206},
  URN =		{urn:nbn:de:0030-drops-205059},
  doi =		{10.4230/DagRep.14.2.206},
  annote =	{Keywords: Applied Topology, Topological Data Analysis, Discrete Morse Theory, Combinatorial Topology, Statistics}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.37
A Generalization of the Persistent Laplacian to Simplicial Maps

Authors: Aziz Burak Gülen, Facundo Mémoli, Zhengchao Wan, and Yusu Wang

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

Abstract
The (combinatorial) graph Laplacian is a fundamental object in the analysis of, and optimization on, graphs. Via a topological view, this operator can be extended to a simplicial complex K and therefore offers a way to perform "signal processing" on p-(co)chains of K. Recently, the concept of persistent Laplacian was proposed and studied for a pair of simplicial complexes K ↪ L connected by an inclusion relation, further broadening the use of Laplace-based operators. In this paper, we significantly expand the scope of the persistent Laplacian by generalizing it to a pair of weighted simplicial complexes connected by a weight preserving simplicial map f: K → L. Such a simplicial map setting arises frequently, e.g., when relating a coarsened simplicial representation with an original representation, or the case when the two simplicial complexes are spanned by different point sets, i.e. cases in which it does not hold that K ⊂ L. However, the simplicial map setting is much more challenging than the inclusion setting since the underlying algebraic structure is much more complicated. We present a natural generalization of the persistent Laplacian to the simplicial setting. To shed insight on the structure behind it, as well as to develop an algorithm to compute it, we exploit the relationship between the persistent Laplacian and the Schur complement of a matrix. A critical step is to view the Schur complement as a functorial way of restricting a self-adjoint positive semi-definite operator to a given subspace. As a consequence of this relation, we prove that the qth persistent Betti number of the simplicial map f: K → L equals the nullity of the qth persistent Laplacian Δ_q^{K,L}. We then propose an algorithm for finding the matrix representation of Δ_q^{K,L} which in turn yields a fundamentally different algorithm for computing the qth persistent Betti number of a simplicial map. Finally, we study the persistent Laplacian on simplicial towers under weight-preserving simplicial maps and establish monotonicity results for their eigenvalues.
Cite as

Aziz Burak Gülen, Facundo Mémoli, Zhengchao Wan, and Yusu Wang. A Generalization of the Persistent Laplacian to Simplicial Maps. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gulen_et_al:LIPIcs.SoCG.2023.37,
  author =	{G\"{u}len, Aziz Burak and M\'{e}moli, Facundo and Wan, Zhengchao and Wang, Yusu},
  title =	{{A Generalization of the Persistent Laplacian to Simplicial Maps}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{37:1--37:17},
  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.37},
  URN =		{urn:nbn:de:0030-drops-178877},
  doi =		{10.4230/LIPIcs.SoCG.2023.37},
  annote =	{Keywords: combinatorial Laplacian, persistent Laplacian, Schur complement, persistent homology, persistent Betti number}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.14
Approximation Algorithms for 1-Wasserstein Distance Between Persistence Diagrams

Authors: Samantha Chen and Yusu Wang

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
Recent years have witnessed a tremendous growth using topological summaries, especially the persistence diagrams (encoding the so-called persistent homology) for analyzing complex shapes. Intuitively, persistent homology maps a potentially complex input object (be it a graph, an image, or a point set and so on) to a unified type of feature summary, called the persistence diagrams. One can then carry out downstream data analysis tasks using such persistence diagram representations. A key problem is to compute the distance between two persistence diagrams efficiently. In particular, a persistence diagram is essentially a multiset of points in the plane, and one popular distance is the so-called 1-Wasserstein distance between persistence diagrams. In this paper, we present two algorithms to approximate the 1-Wasserstein distance for persistence diagrams in near-linear time. These algorithms primarily follow the same ideas as two existing algorithms to approximate optimal transport between two finite point-sets in Euclidean spaces via randomly shifted quadtrees. We show how these algorithms can be effectively adapted for the case of persistence diagrams. Our algorithms are much more efficient than previous exact and approximate algorithms, both in theory and in practice, and we demonstrate its efficiency via extensive experiments. They are conceptually simple and easy to implement, and the code is publicly available in github.
Cite as

Samantha Chen and Yusu Wang. Approximation Algorithms for 1-Wasserstein Distance Between Persistence Diagrams. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.SEA.2021.14,
  author =	{Chen, Samantha and Wang, Yusu},
  title =	{{Approximation Algorithms for 1-Wasserstein Distance Between Persistence Diagrams}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.14},
  URN =		{urn:nbn:de:0030-drops-137861},
  doi =		{10.4230/LIPIcs.SEA.2021.14},
  annote =	{Keywords: persistence diagrams, approximation algorithms, Wasserstein distance, optimal transport}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.26
Elder-Rule-Staircodes for Augmented Metric Spaces

Authors: Chen Cai, Woojin Kim, Facundo Mémoli, and Yusu Wang

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

Abstract
An augmented metric space (X, d_X, f_X) is a metric space (X, d_X) equipped with a function f_X: X → ℝ. It arises commonly in practice, e.g, a point cloud X in ℝ^d where each point x∈ X has a density function value f_X(x) associated to it. Such an augmented metric space naturally gives rise to a 2-parameter filtration. However, the resulting 2-parameter persistence module could still be of wild representation type, and may not have simple indecomposables. In this paper, motivated by the elder-rule for the zeroth homology of a 1-parameter filtration, we propose a barcode-like summary, called the elder-rule-staircode, as a way to encode the zeroth homology of the 2-parameter filtration induced by a finite augmented metric space. Specifically, given a finite (X, d_X, f_X), its elder-rule-staircode consists of n = |X| number of staircase-like blocks in the plane. We show that the fibered barcode, the fibered merge tree, and the graded Betti numbers associated to the zeroth homology of the 2-parameter filtration induced by (X, d_X, f_X) can all be efficiently computed once the elder-rule-staircode is given. Furthermore, for certain special cases, this staircode corresponds exactly to the set of indecomposables of the zeroth homology of the 2-parameter filtration. Finally, we develop and implement an efficient algorithm to compute the elder-rule-staircode in O(n²log n) time, which can be improved to O(n²α(n)) if X is from a fixed dimensional Euclidean space ℝ^d, where α(n) is the inverse Ackermann function.
Cite as

Chen Cai, Woojin Kim, Facundo Mémoli, and Yusu Wang. Elder-Rule-Staircodes for Augmented Metric Spaces. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.SoCG.2020.26,
  author =	{Cai, Chen and Kim, Woojin and M\'{e}moli, Facundo and Wang, Yusu},
  title =	{{Elder-Rule-Staircodes for Augmented Metric Spaces}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{26:1--26: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.26},
  URN =		{urn:nbn:de:0030-drops-121848},
  doi =		{10.4230/LIPIcs.SoCG.2020.26},
  annote =	{Keywords: Persistent homology, Multiparameter persistence, Barcodes, Elder rule, Hierarchical clustering, Graded Betti numbers}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.36
An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology

Authors: Tamal K. Dey, Tianqi Li, and Yusu Wang

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

Abstract
This paper focuses on developing an efficient algorithm for analyzing a directed network (graph) from a topological viewpoint. A prevalent technique for such topological analysis involves computation of homology groups and their persistence. These concepts are well suited for spaces that are not directed. As a result, one needs a concept of homology that accommodates orientations in input space. Path-homology developed for directed graphs by Grigoryan, Lin, Muranov and Yau has been effectively adapted for this purpose recently by Chowdhury and Mémoli. They also give an algorithm to compute this path-homology. Our main contribution in this paper is an algorithm that computes this path-homology and its persistence more efficiently for the 1-dimensional (H₁) case. In developing such an algorithm, we discover various structures and their efficient computations that aid computing the 1-dimensional path-homology. We implement our algorithm and present some preliminary experimental results.
Cite as

Tamal K. Dey, Tianqi Li, and Yusu Wang. An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2020.36,
  author =	{Dey, Tamal K. and Li, Tianqi and Wang, Yusu},
  title =	{{An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{36:1--36: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.36},
  URN =		{urn:nbn:de:0030-drops-121944},
  doi =		{10.4230/LIPIcs.SoCG.2020.36},
  annote =	{Keywords: computational topology, directed graph, path homology, persistent path homology}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.29
Local Cliques in ER-Perturbed Random Geometric Graphs

Authors: Matthew Kahle, Minghao Tian, and Yusu Wang

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We study a random graph model introduced in [Srinivasan Parthasarathy et al., 2017] where one adds Erdős - Rényi (ER) type perturbation to a random geometric graph. More precisely, assume G_X^* is a random geometric graph sampled from a nice measure on a metric space X = (X,d). An ER-perturbed random geometric graph G^(p,q) is generated by removing each existing edge from G_X^* with probability p, while inserting each non-existent edge to G_X^* with probability q. We consider a localized version of clique number for G^(p,q): Specifically, we study the edge clique number for each edge in a graph, defined as the size of the largest clique(s) in the graph containing that edge. We show that the edge clique number presents two fundamentally different types of behaviors in G^(p,q), depending on which "type" of randomness it is generated from. As an application of the above results, we show that by a simple filtering process based on the edge clique number, we can recover the shortest-path metric of the random geometric graph G_X^* within a multiplicative factor of 3 from an ER-perturbed observed graph G^(p,q), for a significantly wider range of insertion probability q than what is required in [Srinivasan Parthasarathy et al., 2017].
Cite as

Matthew Kahle, Minghao Tian, and Yusu Wang. Local Cliques in ER-Perturbed Random Geometric Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kahle_et_al:LIPIcs.ISAAC.2019.29,
  author =	{Kahle, Matthew and Tian, Minghao and Wang, Yusu},
  title =	{{Local Cliques in ER-Perturbed Random Geometric Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{29:1--29:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.29},
  URN =		{urn:nbn:de:0030-drops-115253},
  doi =		{10.4230/LIPIcs.ISAAC.2019.29},
  annote =	{Keywords: random graphs, random geometric graphs, edge clique number, the probabilistic method, metric recovery}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.83
FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees

Authors: Elena Farahbakhsh Touli and Yusu Wang

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
The Gromov-Hausdorff distance is a natural way to measure the distortion between two metric spaces. However, there has been only limited algorithmic development to compute or approximate this distance. We focus on computing the Gromov-Hausdorff distance between two metric trees. Roughly speaking, a metric tree is a metric space that can be realized by the shortest path metric on a tree. Any finite tree with positive edge weight can be viewed as a metric tree where the weight is treated as edge length and the metric is the induced shortest path metric in the tree. Previously, Agarwal et al. showed that even for trees with unit edge length, it is NP-hard to approximate the Gromov-Hausdorff distance between them within a factor of 3. In this paper, we present a fixed-parameter tractable (FPT) algorithm that can approximate the Gromov-Hausdorff distance between two general metric trees within a multiplicative factor of 14. Interestingly, the development of our algorithm is made possible by a connection between the Gromov-Hausdorff distance for metric trees and the interleaving distance for the so-called merge trees. The merge trees arise in practice naturally as a simple yet meaningful topological summary (it is a variant of the Reeb graphs and contour trees), and are of independent interest. It turns out that an exact or approximation algorithm for the interleaving distance leads to an approximation algorithm for the Gromov-Hausdorff distance. One of the key contributions of our work is that we re-define the interleaving distance in a way that makes it easier to develop dynamic programming approaches to compute it. We then present a fixed-parameter tractable algorithm to compute the interleaving distance between two merge trees exactly, which ultimately leads to an FPT-algorithm to approximate the Gromov-Hausdorff distance between two metric trees. This exact FPT-algorithm to compute the interleaving distance between merge trees is of interest itself, as it is known that it is NP-hard to approximate it within a factor of 3, and previously the best known algorithm has an approximation factor of O(sqrt{n}) even for trees with unit edge length.
Cite as

Elena Farahbakhsh Touli and Yusu Wang. FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 83:1-83:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{farahbakhshtouli_et_al:LIPIcs.ESA.2019.83,
  author =	{Farahbakhsh Touli, Elena and Wang, Yusu},
  title =	{{FPT-Algorithms for Computing Gromov-Hausdorff and Interleaving Distances Between Trees}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{83:1--83:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.83},
  URN =		{urn:nbn:de:0030-drops-112048},
  doi =		{10.4230/LIPIcs.ESA.2019.83},
  annote =	{Keywords: Gromov-Hausdorff distance, Interleaving distance, Merge trees}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SoCG.2019
LIPIcs, Volume 129, SoCG'19, Complete Volume

Authors: Gill Barequet and Yusu Wang

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
LIPIcs, Volume 129, SoCG'19, Complete Volume
Cite as

35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{barequet_et_al:LIPIcs.SoCG.2019,
  title =	{{LIPIcs, Volume 129, SoCG'19, Complete Volume}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019},
  URN =		{urn:nbn:de:0030-drops-105562},
  doi =		{10.4230/LIPIcs.SoCG.2019},
  annote =	{Keywords: Theory of computation, Computational geometry, Design and analysis of algorithms, Mathematics of computing, Combinatorics, Graph algortihms}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SoCG.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Gill Barequet and Yusu Wang

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barequet_et_al:LIPIcs.SoCG.2019.0,
  author =	{Barequet, Gill and Wang, Yusu},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.0},
  URN =		{urn:nbn:de:0030-drops-104047},
  doi =		{10.4230/LIPIcs.SoCG.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.3
Vietoris-Rips and Cech Complexes of Metric Gluings

Authors: Michal Adamaszek, Henry Adams, Ellen Gasparovic, Maria Gommel, Emilie Purvine, Radmila Sazdanovic, Bei Wang, Yusu Wang, and Lori Ziegelmeier

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

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

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
DOI: 10.4230/LIPIcs.SoCG.2018.31
Graph Reconstruction by Discrete Morse Theory

Authors: Tamal K. Dey, Jiayuan Wang, and Yusu Wang

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

Abstract
Recovering hidden graph-like structures from potentially noisy data is a fundamental task in modern data analysis. Recently, a persistence-guided discrete Morse-based framework to extract a geometric graph from low-dimensional data has become popular. However, to date, there is very limited theoretical understanding of this framework in terms of graph reconstruction. This paper makes a first step towards closing this gap. Specifically, first, leveraging existing theoretical understanding of persistence-guided discrete Morse cancellation, we provide a simplified version of the existing discrete Morse-based graph reconstruction algorithm. We then introduce a simple and natural noise model and show that the aforementioned framework can correctly reconstruct a graph under this noise model, in the sense that it has the same loop structure as the hidden ground-truth graph, and is also geometrically close. We also provide some experimental results for our simplified graph-reconstruction algorithm.
Cite as

Tamal K. Dey, Jiayuan Wang, and Yusu Wang. Graph Reconstruction by Discrete Morse Theory. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2018.31,
  author =	{Dey, Tamal K. and Wang, Jiayuan and Wang, Yusu},
  title =	{{Graph Reconstruction by Discrete Morse Theory}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{31:1--31: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.31},
  URN =		{urn:nbn:de:0030-drops-87443},
  doi =		{10.4230/LIPIcs.SoCG.2018.31},
  annote =	{Keywords: graph reconstruction, discrete Morse theory, persistence}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.23
Declutter and Resample: Towards Parameter Free Denoising

Authors: Mickael Buchet, Tamal K. Dey, Jiayuan Wang, and Yusu Wang

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
In many data analysis applications the following scenario is commonplace: we are given a point set that is supposed to sample a hidden ground truth K in a metric space, but it got corrupted with noise so that some of the data points lie far away from K creating outliers also termed as ambient noise. One of the main goals of denoising algorithms is to eliminate such noise so that the curated data lie within a bounded Hausdorff distance of K. Popular denoising approaches such as deconvolution and thresholding often require the user to set several parameters and/or to choose an appropriate noise model while guaranteeing only asymptotic convergence. Our goal is to lighten this burden as much as possible while ensuring theoretical guarantees in all cases. Specifically, first, we propose a simple denoising algorithm that requires only a single parameter but provides a theoretical guarantee on the quality of the output on general input points. We argue that this single parameter cannot be avoided. We next present a simple algorithm that avoids even this parameter by paying for it with a slight strengthening of the sampling condition on the input points which is not unrealistic. We also provide some preliminary empirical evidence that our algorithms are effective in practice.
Cite as

Mickael Buchet, Tamal K. Dey, Jiayuan Wang, and Yusu Wang. Declutter and Resample: Towards Parameter Free Denoising. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SoCG.2017.23,
  author =	{Buchet, Mickael and Dey, Tamal K. and Wang, Jiayuan and Wang, Yusu},
  title =	{{Declutter and Resample: Towards Parameter Free Denoising}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.23},
  URN =		{urn:nbn:de:0030-drops-72133},
  doi =		{10.4230/LIPIcs.SoCG.2017.23},
  annote =	{Keywords: denoising, parameter free, k-distance,compact sets}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.36
Topological Analysis of Nerves, Reeb Spaces, Mappers, and Multiscale Mappers

Authors: Tamal K. Dey, Facundo Mémoli, and Yusu Wang

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Data analysis often concerns not only the space where data come from, but also various types of maps attached to data. In recent years, several related structures have been used to study maps on data, including Reeb spaces, mappers and multiscale mappers. The construction of these structures also relies on the so-called nerve of a cover of the domain. In this paper, we aim to analyze the topological information encoded in these structures in order to provide better understanding of these structures and facilitate their practical usage. More specifically, we show that the one-dimensional homology of the nerve complex N(U) of a path-connected cover U of a domain X cannot be richer than that of the domain X itself. Intuitively, this result means that no new H_1-homology class can be "created" under a natural map from X to the nerve complex N(U). Equipping X with a pseudometric d, we further refine this result and characterize the classes of H_1(X) that may survive in the nerve complex using the notion of size of the covering elements in U. These fundamental results about nerve complexes then lead to an analysis of the H_1-homology of Reeb spaces, mappers and multiscale mappers. The analysis of H_1-homology groups unfortunately does not extend to higher dimensions. Nevertheless, by using a map-induced metric, establishing a Gromov-Hausdorff convergence result between mappers and the domain, and interleaving relevant modules, we can still analyze the persistent homology groups of (multiscale) mappers to establish a connection to Reeb spaces.
Cite as

Tamal K. Dey, Facundo Mémoli, and Yusu Wang. Topological Analysis of Nerves, Reeb Spaces, Mappers, and Multiscale Mappers. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2017.36,
  author =	{Dey, Tamal K. and M\'{e}moli, Facundo and Wang, Yusu},
  title =	{{Topological Analysis of Nerves, Reeb Spaces, Mappers, and Multiscale Mappers}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.36},
  URN =		{urn:nbn:de:0030-drops-72220},
  doi =		{10.4230/LIPIcs.SoCG.2017.36},
  annote =	{Keywords: Topology, Nerves, Mapper, Multiscale Mapper, Reeb Spaces}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.53
A Quest to Unravel the Metric Structure Behind Perturbed Networks

Authors: Srinivasan Parthasarathy, David Sivakoff, Minghao Tian, and Yusu Wang

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Graphs and network data are ubiquitous across a wide spectrum of scientific and application domains. Often in practice, an input graph can be considered as an observed snapshot of a (potentially continuous) hidden domain or process. Subsequent analysis, processing, and inferences are then performed on this observed graph. In this paper we advocate the perspective that an observed graph is often a noisy version of some discretized 1-skeleton of a hidden domain, and specifically we will consider the following natural network model: We assume that there is a true graph G^* which is a certain proximity graph for points sampled from a hidden domain X; while the observed graph G is an Erdos-Renyi type perturbed version of G^*. Our network model is related to, and slightly generalizes, the much-celebrated small-world network model originally proposed by Watts and Strogatz. However, the main question we aim to answer is orthogonal to the usual studies of network models (which often focuses on characterizing / predicting behaviors and properties of real-world networks). Specifically, we aim to recover the metric structure of G^* (which reflects that of the hidden space X as we will show) from the observed graph G. Our main result is that a simple filtering process based on the Jaccard index can recover this metric within a multiplicative factor of 2 under our network model. Our work makes one step towards the general question of inferring structure of a hidden space from its observed noisy graph representation. In addition, our results also provide a theoretical understanding for Jaccard-Index-based denoising approaches.
Cite as

Srinivasan Parthasarathy, David Sivakoff, Minghao Tian, and Yusu Wang. A Quest to Unravel the Metric Structure Behind Perturbed Networks. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{parthasarathy_et_al:LIPIcs.SoCG.2017.53,
  author =	{Parthasarathy, Srinivasan and Sivakoff, David and Tian, Minghao and Wang, Yusu},
  title =	{{A Quest to Unravel the Metric Structure Behind Perturbed Networks}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.53},
  URN =		{urn:nbn:de:0030-drops-72112},
  doi =		{10.4230/LIPIcs.SoCG.2017.53},
  annote =	{Keywords: metric structure, Erd\"{o}s-R\'{e}nyi perturbation, graphs, doubling measure}
}
Document
Multimedia Contribution
DOI: 10.4230/LIPIcs.SoCG.2017.65
Cardiac Trabeculae Segmentation: an Application of Computational Topology (Multimedia Contribution)

Authors: Chao Chen, Dimitris Metaxas, Yusu Wang, and Pengxiang Wu

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
In this video, we present a research project on cardiac trabeculae segmentation. Trabeculae are fine muscle columns within human ventricles whose both ends are attached to the wall. Extracting these structures are very challenging even with state-of-the-art image segmentation techniques. We observed that these structures form natural topological handles. Based on such observation, we developed a topological approach, which employs advanced computational topology methods and achieve high quality segmentation results.
Cite as

Chao Chen, Dimitris Metaxas, Yusu Wang, and Pengxiang Wu. Cardiac Trabeculae Segmentation: an Application of Computational Topology (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 65:1-65:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.SoCG.2017.65,
  author =	{Chen, Chao and Metaxas, Dimitris and Wang, Yusu and Wu, Pengxiang},
  title =	{{Cardiac Trabeculae Segmentation: an Application of Computational Topology}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{65:1--65:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.65},
  URN =		{urn:nbn:de:0030-drops-72429},
  doi =		{10.4230/LIPIcs.SoCG.2017.65},
  annote =	{Keywords: image segmentation, trabeculae, persistent homology, homology localization}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.35
SimBa: An Efficient Tool for Approximating Rips-Filtration Persistence via Simplicial Batch-Collapse

Authors: Tamal K. Dey, Dayu Shi, and Yusu Wang

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

Abstract
In topological data analysis, a point cloud data P extracted from a metric space is often analyzed by computing the persistence diagram or barcodes of a sequence of Rips complexes built on P indexed by a scale parameter. Unfortunately, even for input of moderate size, the size of the Rips complex may become prohibitively large as the scale parameter increases. Starting with the Sparse Rips filtration introduced by Sheehy, some existing methods aim to reduce the size of the complex so as to improve the time efficiency as well. However, as we demonstrate, existing approaches still fall short of scaling well, especially for high dimensional data. In this paper, we investigate the advantages and limitations of existing approaches. Based on insights gained from the experiments, we propose an efficient new algorithm, called SimBa, for approximating the persistent homology of Rips filtrations with quality guarantees. Our new algorithm leverages a batch collapse strategy as well as a new sparse Rips-like filtration. We experiment on a variety of low and high dimensional data sets. We show that our strategy presents a significant size reduction, and our algorithm for approximating Rips filtration persistence is order of magnitude faster than existing methods in practice.
Cite as

Tamal K. Dey, Dayu Shi, and Yusu Wang. SimBa: An Efficient Tool for Approximating Rips-Filtration Persistence via Simplicial Batch-Collapse. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ESA.2016.35,
  author =	{Dey, Tamal K. and Shi, Dayu and Wang, Yusu},
  title =	{{SimBa: An Efficient Tool for Approximating  Rips-Filtration Persistence via Simplicial Batch-Collapse}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{35:1--35: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.35},
  URN =		{urn:nbn:de:0030-drops-63869},
  doi =		{10.4230/LIPIcs.ESA.2016.35},
  annote =	{Keywords: Rips filtration, Homology groups, Persistence, Topological data analysis}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.461
Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs

Authors: Ulrich Bauer, Elizabeth Munch, and Yusu Wang

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

Abstract
The Reeb graph is a construction that studies a topological space through the lens of a real valued function. It has been commonly used in applications, however its use on real data means that it is desirable and increasingly necessary to have methods for comparison of Reeb graphs. Recently, several metrics on the set of Reeb graphs have been proposed. In this paper, we focus on two: the functional distortion distance and the interleaving distance. The former is based on the Gromov-Hausdorff distance, while the latter utilizes the equivalence between Reeb graphs and a particular class of cosheaves. However, both are defined by constructing a near-isomorphism between the two graphs of study. In this paper, we show that the two metrics are strongly equivalent on the space of Reeb graphs. Our result also implies the bottleneck stability for persistence diagrams in terms of the Reeb graph interleaving distance.
Cite as

Ulrich Bauer, Elizabeth Munch, and Yusu Wang. Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 461-475, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.SOCG.2015.461,
  author =	{Bauer, Ulrich and Munch, Elizabeth and Wang, Yusu},
  title =	{{Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{461--475},
  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.461},
  URN =		{urn:nbn:de:0030-drops-51467},
  doi =		{10.4230/LIPIcs.SOCG.2015.461},
  annote =	{Keywords: Reeb graph, interleaving distance, functional distortion distance}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.491
Comparing Graphs via Persistence Distortion

Authors: Tamal K. Dey, Dayu Shi, and Yusu Wang

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

Abstract
Metric graphs are ubiquitous in science and engineering. For example, many data are drawn from hidden spaces that are graph-like, such as the cosmic web. A metric graph offers one of the simplest yet still meaningful ways to represent the non-linear structure hidden behind the data. In this paper, we propose a new distance between two finite metric graphs, called the persistence-distortion distance, which draws upon a topological idea. This topological perspective along with the metric space viewpoint provide a new angle to the graph matching problem. Our persistence-distortion distance has two properties not shared by previous methods: First, it is stable against the perturbations of the input graph metrics. Second, it is a continuous distance measure, in the sense that it is defined on an alignment of the underlying spaces of input graphs, instead of merely their nodes. This makes our persistence-distortion distance robust against, for example, different discretizations of the same underlying graph. Despite considering the input graphs as continuous spaces, that is, taking all points into account, we show that we can compute the persistence-distortion distance in polynomial time. The time complexity for the discrete case where only graph nodes are considered is much faster.
Cite as

Tamal K. Dey, Dayu Shi, and Yusu Wang. Comparing Graphs via Persistence Distortion. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 491-506, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SOCG.2015.491,
  author =	{Dey, Tamal K. and Shi, Dayu and Wang, Yusu},
  title =	{{Comparing Graphs via Persistence Distortion}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{491--506},
  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.491},
  URN =		{urn:nbn:de:0030-drops-51285},
  doi =		{10.4230/LIPIcs.SOCG.2015.491},
  annote =	{Keywords: Graph matching, metric graphs, persistence distortion, topological method}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.796
Maintaining Contour Trees of Dynamic Terrains

Authors: Pankaj K. Agarwal, Thomas Mølhave, Morten Revsbæk, Issam Safa, Yusu Wang, and Jungwoo Yang

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

Abstract
We study the problem of maintaining the contour tree T of a terrain Sigma, represented as a triangulated xy-monotone surface, as the heights of its vertices vary continuously with time. We characterize the combinatorial changes in T and how they relate to topological changes in Sigma. We present a kinetic data structure (KDS) for maintaining T efficiently. It maintains certificates that fail, i.e., an event occurs, only when the heights of two adjacent vertices become equal or two saddle vertices appear on the same contour. Assuming that the heights of two vertices of Sigma become equal only O(1) times and these instances can be computed in O(1) time, the KDS processes O(kappa + n) events, where n is the number of vertices in Sigma and kappa is the number of events at which the combinatorial structure of T changes, and processes each event in O(log n) time. The KDS can be extended to maintain an augmented contour tree and a join/split tree.
Cite as

Pankaj K. Agarwal, Thomas Mølhave, Morten Revsbæk, Issam Safa, Yusu Wang, and Jungwoo Yang. Maintaining Contour Trees of Dynamic Terrains. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 796-811, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SOCG.2015.796,
  author =	{Agarwal, Pankaj K. and M{\o}lhave, Thomas and Revsb{\ae}k, Morten and Safa, Issam and Wang, Yusu and Yang, Jungwoo},
  title =	{{Maintaining Contour Trees of Dynamic Terrains}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{796--811},
  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.796},
  URN =		{urn:nbn:de:0030-drops-51406},
  doi =		{10.4230/LIPIcs.SOCG.2015.796},
  annote =	{Keywords: Contour tree, dynamic terrain, kinetic data structure}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.827
Topological Analysis of Scalar Fields with Outliers

Authors: Mickaël Buchet, Frédéric Chazal, Tamal K. Dey, Fengtao Fan, Steve Y. Oudot, and Yusu Wang

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

Abstract
Given a real-valued function f defined over a manifold M embedded in R^d, we are interested in recovering structural information about f from the sole information of its values on a finite sample P. Existing methods provide approximation to the persistence diagram of f when geometric noise and functional noise are bounded. However, they fail in the presence of aberrant values, also called outliers, both in theory and practice. We propose a new algorithm that deals with outliers. We handle aberrant functional values with a method inspired from the k-nearest neighbors regression and the local median filtering, while the geometric outliers are handled using the distance to a measure. Combined with topological results on nested filtrations, our algorithm performs robust topological analysis of scalar fields in a wider range of noise models than handled by current methods. We provide theoretical guarantees and experimental results on the quality of our approximation of the sampled scalar field.
Cite as

Mickaël Buchet, Frédéric Chazal, Tamal K. Dey, Fengtao Fan, Steve Y. Oudot, and Yusu Wang. Topological Analysis of Scalar Fields with Outliers. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 827-841, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SOCG.2015.827,
  author =	{Buchet, Micka\"{e}l and Chazal, Fr\'{e}d\'{e}ric and Dey, Tamal K. and Fan, Fengtao and Oudot, Steve Y. and Wang, Yusu},
  title =	{{Topological Analysis of Scalar Fields with Outliers}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{827--841},
  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.827},
  URN =		{urn:nbn:de:0030-drops-51052},
  doi =		{10.4230/LIPIcs.SOCG.2015.827},
  annote =	{Keywords: Persistent Homology, Topological Data Analysis, Scalar Field Analysis, Nested Rips Filtration, Distance to a Measure}
}
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