This workshop focuses on recent advances in diverse areas of computational topology. The application of topological techniques to traditional data analysis, as well as the growing use of algorithmic topology in theoretical mathematics, has led to a boost in research in the topic. As part of CG Week, the workshop emphasizes the connections of computational topology to discrete and computational geometry.
The workshop will potentially include the following non-exhaustive
list of topics, and their interaction with computational topology:
persistent homology, topological data analysis, low-dimensional
topology, statistics and category theory.
This year, the workshop will focus on two main themes: low-dimensional topology and the theory of persistence.
Vanessa Robins, Stephan Tillmann, Benjamin Burton, Chao Chen, Robert Haraway, Tim Ophelders, Steve Oudot, William Pettersson, Yusu Wang
(Hierarchical-) Clustering consistently: Densities and graphons
Hierarchical clustering is a common way to assist data analysis. Numerous hierarchical clustering methods have been proposed in the literature. However, only limited work has been developed towards a general theory to study (statistical) consistency of hierarchical clustering algorithms. For example, given data generated in a certain way and a specific hierarchical-clustering algorithm, does the output of the algorithm converges to the ``true'' hierarchical clustering structure as there are more and more data? Naturally, the answer to such questions depends on the specific model to generate input data. In this talk, I will present some of our recent work in this direction, where we investigate the consistency of hierarchical clustering for two types of data: point-data sampled from a density distribution, and graphs generated from graphons. We will describe not only the theoretical frameworks to study such questions, but also algorithms that are consistent under our models.
This is joint work with Mikhail Belkin and Justin Eldridge.
Finite state computational topology
Crushing and inflating triangulations
In 2003 Jaco and Rubinstein introduced the notion of 0-efficient triangulations, triangulations which contain a minimal number of vertices. For closed manifolds (that are not S^3), 0-efficient triangulations have one vertex.
For manifolds with boundary, 0-efficient triangulations have all their vertices in the boundary, and exactly one vertex in each boundary component.
To investigate this, they introduced the crushing technique which, given a triangulation T of a manifold M, can produce a related ideal triangulation \circ T of the interior of M.
This crushing technique not only produces a related triangulation, but also ensures that the crushed triangulation contains fewer tetrahedra than the original, which has obvious algorithmic benefits.
This technique has been implemented in popular topological software and can be used for 3-sphere recognition, amongst other things
More recently, Jaco and Rubinstein demonstrated the inflation operation, which can be thought of as an inverse to crushing.
As crushing does destroy information relating to the boundary of the triangulation, it is not a perfect inverse function.
In this talk I will give an intuitive understanding of the crushing and inflation techniques, as well as a walk-through explanation of the algorithm behind inflations as soon-to-be implemented in Regina.
Cardiac Trabeculae Segmentation: An Application of Computational Topology
In cardiac image analysis, it is important yet challenging to reconstruct the trabeculae, namely, fine muscle columns whose ends are attached to the ventricular walls. To extract these fine structures, traditional image segmentation methods are insufficient. We propose to detect salient topological handles based on persistent homology. Furthermore, we propose to compute the optimal representations of these handles. To this end, we propose a general-purpose algorithm that efficiently computes the shortest representative cycle of a persistence dot. We validate our contribution by comparing with previous standard segmentation methods without topological priors, as well as topological method without the optimal representations.
Computing trisections of 4-manifolds
The world of 4-dimensional manifolds is still a bit like the Wild
West. Many important problems - as well as the decidability of these
problems - are still open. Gay and Kirby recently introduced a new
structure theory for 4-manifolds called trisections. I will report on work
in progress with Mark Bell, Joel Hass and Hyam Rubinstein on algorithms to
compute trisections and bounds on invariants derived from them.
Persistent homology of spatially random point patterns
A Gaussian Type Kernel for Persistence Diagrams
Persistence diagrams (PDs) play a key role in topological data
analysis (TDA), in which they are routinely used to describe topological
properties of complicated shapes. PDs enjoy strong stability properties
and have proven their utility in various learning contexts. They do
not, however, live in a space naturally endowed with a Hilbert structure
and are usually compared with non-Hilbertian distances, such as the
bottleneck distance. To incorporate PDs in a convex learning pipeline,
several kernels have been proposed with a strong emphasis on the
stability of the resulting RKHS distance w.r.t. perturbations of the
PDs. In this talk, I will show how the Sliced Wasserstein approximation
of the Wasserstein distance can be used to define a new kernel for PDs,
which is not only provably stable but also discriminative w.r.t. the
1-bottleneck distance between PDs. I will then show some experimental
results on several benchmarks, to demonstrate its practicality and to
illustrate how its metric behavior approaches that of the standard Gaussian
kernel. This is joint work with Mathieu Carrière and Marco Cuturi.
Computing the Fréchet distance between real-valued surfaces
The Fréchet distance is a well-studied measure for the similarity of shapes. While efficient algorithms for computing the Fréchet distance between curves exist, there are only few results on the Fréchet distance between surfaces. Recent work has shown that the Fréchet distance is computable between piecewise linear functions f and g from M to ℝᵏ with M a triangulated surface of genus zero. We focus on the case k=1 and M being a topological sphere or disk with constant boundary. Intuitively, we measure the distance between terrains based solely on the height function. Our main result is that in this case computing the Fréchet distance between f and g is in NP.
We additionally show that already for k=1, computing a factor 2-ε approximation of the Fréchet distance is NP-hard, showing that this problem is in fact NP-complete. We also define an intermediate distance, between contour trees, which we also show to be NP-complete to compute. Finally, we discuss how our and other distance measures between contour trees relate to each other.
Advanced Institute for Materials Research
buchet.mickael.laurent.d7 AT tohoku.ac.jp
Emerson G. Escolar
Advanced Institute for Materials Research
escolar.emerson.gaw.d6 AT tohoku.ac.jp
Postdoctoral Research Fellow
School of Mathematics and Physics
University of Queensland
School of Computing
Scientific Computing and Imaging Institute
University of Utah
beiwang AT sci.utah.edu