FoCM 2014 conference

Session B2 - Computational Topology and Geometry

Organizers: Herbert Edelsbrunner (Duke University, USA) - Joel Hass (University of California at Davis, USA) - Alex Nabutovsky (University of Toronto, Canada)

Workshop website

View session abstracts PDF



December 16, 18:00 ~ 18:25 - Room C11

The Classification of Homotopy Classes of Bounded Curvature Paths

José Ayala

UNAP, Chile   -

A bounded curvature path is a continuously differentiable piecewise $C^2$ path with bounded absolute curvature that connects two points in the tangent bundle of a surface. We give necessary and sufficient conditions for two bounded curvature paths, defined in the Euclidean plane, to be in the same connected component while keeping the curvature bounded at every stage of the deformation. This work finishes a program started by Lester Dubins in 1961.

Joint work with Hyam Rubinstein (University of Melbourne, Australia).

View abstract PDF

December 15, 15:30 ~ 15:55 - Room A22

Induced Matchings of Barcodes and the Algebraic Stability of Persistence

Ulrich Bauer

TU München, Germany   -

We define a simple, explicit map sending a morphism $f: M \to N$ of pointwise finite dimensional persistence modules to a matching between the barcodes of $M$ and $N$. Our main result is that, in a precise sense, the quality of this matching is tightly controlled by the lengths of the longest intervals in the barcodes of $\ker f$ and $\mathop{\mathrm{coker}} f$. As an immediate corollary, we obtain a new proof of the algebraic stability of persistence, a fundamental result in the theory of persistent homology. In contrast to previous proofs, ours shows explicitly how a $\delta$-interleaving morphism between two persistence modules induces a $\delta$-matching between the barcodes of the two modules. Our main result also specializes to a structure theorem for submodules and quotients of persistence modules.

Joint work with Michael Lesnick (IMA, Minneapolis, MN).

View abstract PDF

December 17, 17:30 ~ 17:55 - Room A22

Parameterised complexity in 3-manifold topology

Benjamin Burton

The University of Queensland, Australia   -

Decision problems on 3-manifolds are notoriously difficult: the mere existence of an algorithm is often a major result, even ``simple'' problems have best-known algorithms that are exponential time, and many important algorithms have yet to be studied from a complexity viewpoint. In practice, however, some of these algorithms run surprisingly well in experimental settings. In this talk we discuss why parameterised complexity now looks to be the ``right'' tool to explain this behaviour. We present encouraging initial results on the parameterised complexity of topological problems, including both fixed-parameter-tractability and W[P]-hardness results, and discuss current directions of ongoing research.

Joint work with Rodney Downey (Victoria University of Wellington, New Zealand), Thomas Lewiner (PUC University of Rio de Janeiro, Brazil), João Paixão (PUC University of Rio de Janeiro, Brazil), William Pettersson (The University of Queensland, Australia) and Jonathan Spreer (The University of Queensland, Australia).

View abstract PDF

December 15, 18:00 ~ 18:25 - Room A22

Variations on Topological Complexity

Hellen Colman

Wright College, Chicago, USA   -

We give a succinct introduction to Farber's topological complexity. This number is a homotopy invariant which reflects the complexity of the problem of constructing a motion planning algorithm in the configuration space of a mechanical system. We introduce a groupoid invariant carrying an interpretation in terms of the motion planning problem for a robot when its configuration space exhibits symmetries. This number is an interesting invariant in itself to measure the complexity of motion planning algorithms in situations that might be modeled by a group action. In particular it could provide a model for the planning of a robot transporting itself by means of two different types of motions. For example, a model for a robot traveling in the physical space by guided tracks and/or air transportation. This is joint work with Andres Angel.

Joint work with Andres Angel (Universidad de los Andes, Colombia).

View abstract PDF

December 16, 17:00 ~ 17:50 - Room C11

Topology and Geometry of Amorphous Structures

Yasuaki Hiraoka

Kyushu University, Japan   -

Description of amorphous structures has been a long-standing problem. What is lacking there is an appropriate language to describe geometric structures including short-range order (SRO) and medium-range order (MRO). In this talk, we present new computational topological methods to this problem: (1) persistence modules on commutative ladders, and (2) continuations of point clouds by persistence diagrams. These methods elucidate the following new geometric features in amorphous structure: (i) persistence of MRO rings in silica glasses under pressurizations, and (ii) presence of 1-parameter deformations connecting specific packing states (FCC, HCP, 5-rings, etc) in three dimensional granular packing experiments.

View abstract PDF

December 15, 17:00 ~ 17:25 - Room A22

Configuration spaces of hard disks in an infinite strip

Matthew Kahle

Ohio State University, United States   -

We study the configuration space $C(n,w)$ of $n$ non-overlapping unit-diameter disks in an infinite strip of width $w$. We present an asymptotic formula for the $k$th Betti number of $C(n,w)$, for fixed $k$ and $w$ as $n \to \infty$. We find that there is a striking phase transition: for $w > k$ the $k$th homology is stable and is isomorphic to the $k$th homology of the configuration space of points. But for $w \le k$, the $k$th homology is wildly complicated, growing exponentially fast with $n$.

Joint work with Robert MacPherson (Institute for Advanced Study).

View abstract PDF

December 16, 16:00 ~ 16:25 - Room C11

Beyond Convexity: New Perspectives in Computational Optimization

Narenda Karmarkar

, India   -

For computational solutions of convex optimization problems, a rich body of knowledge including theory, algorithms, and computational experience is now available. In contrast, nothing of comparable depth and completeness can be offered at the present time, for non-convex problems. The field of convex optimization benefited immensely from pre-existing body of concepts and knowledge from pure mathematics, while non-convex problems seems to require formulation and exploration of entirely new mathematical concepts, as well as new models of computation. The intent of this paper is to describe our efforts in this direction, at a philosophical or conceptual level, without going into specific applications or implementation in software. We also point out connections with other areas, particularly mathematical physics.

View abstract PDF

December 15, 14:35 ~ 15:25 - Room A22

Measuring the geometric similarities of genus-zero surfaces

Patrice Koehl

University of California, Davis, USA   -

Finding efficient algorithms to describe, measure and compare shapes is a central problem in numerous disciplines that generate extensive quantitative and visual information. Among these, biology occupies a central place. Registration of brain anatomy for example is essential to many studies in neurobiology; at a molecular level, comparison of protein shapes is a key step in understanding the relationships between their functions. In this talk I will introduce the idea of a globally optimal conformal mapping between two (discrete) surfaces of genus zero as one method to solve this problem. In this approach, the whole mesh representing the source surface is warped onto the target surface, using the mapping defined through the composition of discrete conformal mappings of the surfaces onto the sphere and the M\"{o}bius transformation between these mappings. The M\"{o}bius transformation is then optimized to lead to minimal distortion between the source mesh and its image, where distortion is measured as difference from isometry. I will show that this approach leads to the definition of a metric in the space of genus-zero surfaces. I will describe the implementation of this approach and its applications on biological examples, from brain surface matching to testing how round proteins are.

Joint work with Joel Hass (University of California, Davis, USA).

View abstract PDF

December 15, 17:30 ~ 17:55 - Room A22

Random 3-manifolds

Joseph Maher

College of Staten Island, CUNY, USA   -

We discuss some recent results on random 3-manifolds, including recent work on the Casson invariant of random Heegaard splittings.

Joint work with Alexander Lubotzky (Hebrew University) and Conan Wu (Princeton University).

View abstract PDF

December 16, 14:30 ~ 14:55 - Room C11

Distributed Computation of Persistent Homology using the Blowup Complex

Dmitriy Morozov

Lawrence Berkeley National Laboratory, USA   -

This talk will describe an algorithm to distribute computation of persistent homology over multiple processors, by subdividing the domain into regions and combining the results using the Mayer-Vietoris blowup complex.

Joint work with Ryan Lewis (Stanford University) and Gunnar Carlsson (Stanford University).

View abstract PDF

December 16, 15:00 ~ 15:25 - Room C11

Algebraic Morse-Forman-Conley theory

Marian Mrozek

Jagiellonian University, Poland   -

In late 90' R. Forman introduced the concept of a combinatorial vector field on a CW complex and presented a version of Morse theory for acyclic combinatorial vector fields. He also studied combinatorial vector fields without acyclicity assumption, introduced the concept of a chain recurrent set and proved Morse inequalities in this setting.

In years 2005-06 the discrete Morse theory of Forman has been generalized by several authors from the case of CW complexes to the purely algebraic case of chain complexes with a distinguished basis.

In this talk we present the Morse-Conley theory in such a purely algebraic setting. This, in particular, generalizes the definition of an isolated invariant set and its Conley index proposed recently by T. Kaczynski, M. Mrozek and Th. Wanner for simplicial complexes. Moreover, we define attractors, repellers, attractor repeller-pairs, and Morse decompositions and extend to this combinatorial/algebraic setting some classical results of Morse-Conley theory for flows.

View abstract PDF

December 16, 15:30 ~ 15:55 - Room C11

Persistent Objects

Amit Patel

Institute for Advanced Study, USA   -

For a continuous map $f : X \rightarrow R$ to the reals, there is a persistent homology group for each interval $[r,s]$. If $X_r$ is the $r$-sublevel set of $f$ and $X_s$ the $s$-sublevel set of $f$, then the persistent homology group is image of the homomorphism $H_d(X_r) \rightarrow H_d(X_s)$ induced by the inclusion $X_r \subset X_s$. This is the homology that spreads out over the interval $[r,s]$. Recently, it has been shown that the persistent homology group can be defined for any map $f : X \rightarrow M$, where $M$ is an oriented manifold. If $U$ is an open set of $M$, then the persistent homology over $U$ is a subgroup of $H_d(f^{-1}(U))$ that spreads out over $U$. The notion of persistent homology categorifies. Let $F: D \rightarrow C$ be a diagram in a category $C$. Under some mild assumptions on $C$, there is a notion of a persistent object for $F$. This is the object in $C$ that spreads out over then entire diagram. In this talk, I will present the persistent homology group of maps to the reals, the persistent homology group for maps to any oriented manifold, and the persistent object.

View abstract PDF

December 17, 15:30 ~ 15:55 - Room A22

Inducing a map on homology from a correspondence

Paweł Pilarczyk

IST Austria, Austria   -

We define the homomorphism induced in homology by a closed correspondence between topological spaces. For that purpose, we use projections from the graph of the correspondence to its domain and codomain. We focus on correspondences that naturally emerge from combinatorial approximations of continuous maps obtained either by means of rigorous numerics or by an attempt to reconstruct the map from a finite set of data points. We show that under certain assumptions, the homomorphism induced by an outer approximation of a continuous map coincides with the homomorphism induced in homology by the map itself. In particular, our results provide a generalization of the work by Mischaikow, Mrozek and Pilarczyk, published in Found. Comput. Math., Vol. 5, 2005 (pp. 199-229).

Joint work with Shaun Harker (Rutgers University, USA), Hiroshi Kokubu (Kyoto University, Japan) and Konstantin Mischaikow (Rutgers University, USA).

View abstract PDF

December 17, 16:00 ~ 16:25 - Room A22

Practical efficiency of persistent homology computations

Hubert Wagner

IST Austria, Austria   -

In this talk I summarize a number of algorithmic techniques that enhance the efficiency of persistent homology computations. While the existing algorithms are at least quadratic in the number of input cells in the worst case, careful optimizations yield roughly linear behavior for practical data sets. I focus on discrete Morse theoretical preprocessing, which is especially useful for cubical (e.g. image) data. Additionally, efficient variants of the standard matrix reduction algorithm are discussed.

Joint work with Uli Bauer (IST Austria), David Gunther (Télécom ParisTech), Michael Kerber (MPI Saarbrücken) and Jan Reininghaus (IST Austria).

View abstract PDF

December 17, 17:00 ~ 17:25 - Room A22

Embeddings of Simplicial Complexes $- $ Algorithms $\&$ Combinatorics

Uli Wagner

IST Austria, Austria   -

We survey a number of results and open questions concerning (from a combinatorialist's point of view) higher-dimensional analogues of graph planarity and crossing numbers, i.e., embeddings of finite simplicial complexes (compact polyhedra) into Euclidean space and other ambient manifolds.

While embeddings are a classical topic in geometric topology, here we focus rather on algorithmic and combinatorial aspects. Two typical questions are the following:

(1) Is there an algorithm that, given as input a finite k-dimensional simplical complex, decides whether it embeds in d-dimensional space?

(2) What is the maximum number of k-dimensional simplices of a simplicial complex that embeds into d-dimensional space?

Time permitting, we will also discuss some maps with more general restrictions on the set of singularities, e.g., maps without r-fold intersection points.

Joint work with Martin Cadek (Masaryk University, Brno), Xavier Goaoc (Universite Paris-Est), Marek Krcal (IST Austria), Isaac Mabillard (IST Austria), Jiri Matousek (Charles University, Prague), Pavel Patak (Charles University, Prague), Zusana Safernova (Charles University, Prague), Francis Sergeraert (Institut Fourier, Grenoble), Eric Sedgwick (DePaul University, Chicago), Martin Tancer (IST Austria) and Lukas Vokrinek (Masaryk University, Brno).

View abstract PDF