6th Annual Minisymposium on Computational Topology

Brisbane, July 4-7, 2017

Part of Computational Geometry Week (CG Week 2017)

Overview

The Workshop

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.

Main Themes

This year, the workshop will focus on two main themes: low-dimensional topology and the theory of persistence.

Confirmed Speakers

Vanessa Robins, Stephan Tillmann, Benjamin Burton, Chao Chen, Robert Haraway, Tim Ophelders, Steve Oudot, William Pettersson, Yusu Wang

Schedule

Tentative Schedule

Time Speaker Title
14:30 - 15:30 Yusu Wang (Hierarchical-) Clustering consistently: Densities and graphons
15:30 - 16:00 Benjamin Burton Finite state computational topology
16:00 - 16:30 Break
16:30 - 17:00 Robert Haraway A new T2 l test
17:00 - 17:30 William Pettersson Crushing and inflating triangulations
17:30 - 18:00 Chao Chen Cardiac Trabeculae Segmentation: An Application of Computational Topology
July 5, 2017
Time Speaker Title
14:30 - 15:30 Stephan Tillmann Computing trisections of 4-manifolds
15:30 - 16:00 Vanessa Robins Persistent homology of spatially random point patterns
16:00 - 16:30 Break
16:30 - 17:00 Steve Oudot A Gaussian Type Kernel for Persistence Diagrams
17:00 - 17:30 Tim Ophelders Computing the Fréchet distance between real-valued surfaces
17:30 - 18:00 Open Questions and Discussions
July 6, 2017

Abstracts

(Hierarchical-) Clustering consistently: Densities and graphons

Yusu Wang

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

Benjamin Burton

A new T2 l test

Robert Haraway

Crushing and inflating triangulations

William Pettersson

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

Chao Chen

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

Stephan Tillmann

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

Vanessa Robins

A Gaussian Type Kernel for Persistence Diagrams

Steve Oudot

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

Tim Ophelders

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.

Organizers

Mickaël Buchet
Research Associate
Hiraoka Laboratory
Advanced Institute for Materials Research
Tohoku University
buchet.mickael.laurent.d7 AT tohoku.ac.jp

Emerson G. Escolar
Research Associate
Hiraoka Laboratory
Advanced Institute for Materials Research
Tohoku University
escolar.emerson.gaw.d6 AT tohoku.ac.jp

Clément Maria
Postdoctoral Research Fellow
School of Mathematics and Physics
University of Queensland

Bei Wang
Assistant Professor
School of Computing
Scientific Computing and Imaging Institute
University of Utah
beiwang AT sci.utah.edu