Workshop A4 - Computational Geometry and Topology

Organizers: Joel Hass (University of California at Davis, USA) - Herbert Edelsbrunner (Institute of Science and Technology, Austria) - Gunnar Carlsson (Stanford University, USA)

View workshop abstracts PDF



July 10, 14:30 ~ 14:55

Generalized Persistence Diagrams

Amit Patel

Colorado State University, USA   -

We generalize the persistence diagram of Cohen-Steiner, Edelsbrunner, and Harer to the setting of constructible persistence modules valued in a symmetric monoidal category. We call this the type A persistence diagram of a persistence module. If the category is also abelian, then we define a second type B persistence diagram. In addition, we define a new metric between persistence diagrams we call the erosion distance which closely resembles the interleaving distance between persistence modules. We show that our assignment of a type B persistence diagram to a constructible persistence module is $1$-Lipschitz.

View abstract PDF

July 10, 15:00 ~ 15:25

Topological analyses of olfaction and semantic learning

Chad Giusti

University of Pennsylvania, USA   -

I will briefly describe two very different applications of persistent homology in the analysis of neural systems: one to a model of olfactory sensing, and the other to development of semantic networks in children. The former is a work in progress involving some light geometry with points and planes, the latter an application of network filtration by nodes, and will involve the observation that there are two cycles in a network involving turtles and peas.

Joint work with Vladimir Itskov (Pennsylvania State University), Ann Sizemore (University of Pennsylvania), Elisabeth Karuza (University of Pennsylvania) and Danielle Bassett (University of Pennsylvania).

View abstract PDF

July 10, 17:00 ~ 17:25

Universality of the Homotopy Interleaving Distance

Michael Lesnick

Princeton University, USA   -

We introduce and study homotopy interleavings between filtered topological spaces. These are homotopy-invariant analogues of interleavings, objects commonly used in topological data analysis to articulate stability and inference theorems. Intuitively, whereas a strict interleaving between filtered spaces $X$ and $Y$ certifies that $X$ and $Y$ are approximately isomorphic, a homotopy interleaving between $X$ and $Y$ certifies that $X$ and $Y$ are approximately weakly equivalent.

The main results of this paper are that homotopy interleavings induce an extended pseudometric $d_{HI}$ on filtered spaces, and that this is the universal pseudometric satisfying natural stability and homotopy invariance axioms. To motivate these axioms, we also observe that $d_{HI}$ (or more generally, any pseudometric satisfying these two axioms and an additional “homology bounding” axiom) can be used to formulate lifts of fundamental TDA theorems from the algebraic (homological) level to the level of filtered spaces.

Joint work with Andrew J. Blumberg (UT Austin).

View abstract PDF

July 10, 17:30 ~ 17:55

Minimum action principles and shape dynamics

Patrice Koehl

Department of Computer Science, University of California, Davis, USA   -

The functions of all life forms depend on organization in space and time. Spatial organization involves the interactions of shapes with their surroundings, while organization in time concerns changes in shape. Geometric methods therefore play an essential role in the analyses and simulations of biological systems. Geometry and topology are now used regularly for representing, searching, simulating, analyzing, and comparing biological systems. In this talk, I will focus on the latter. I will present a new method for computing a distance between two shapes embedded in three dimensional space. Instead of comparing directly the geometric properties of the two shapes, we measure the cost of deforming one of the two shapes into the other. The deformation is computed as the geodesic between the two shapes in the space of shapes. The geodesic is found as a minimizer of the Onsager Machlup action, based on an elastic energy for shapes. I will illustrate applications of this method to geometric morphometrics using data sets representing bones and teeth of primates. Experiments on these data sets show that the method performs remarkably well both in shape recognition and in identifying evolutionary patterns, with success rates similar to, and in some cases better than, those obtained by expert observers.

View abstract PDF

July 10, 18:00 ~ 18:25

Stabilizing the unstable output of persistent homology computations

Peter Bubenik

University of Florida, United States   -

For data filtered by time or scale, persistent homology provides a succinct summary, the persistence diagram or bar code, which encodes the births and deaths of topological features. Crucially, this summary is stable with respect to perturbations of the data. Persistent homology computations may also provide the locations of these topological features, something of particular interest to practitioners, but these are unfortunately unstable. I will present a general framework for providing stable versions of such calculations.

Joint work with Paul Bendich (Duke University) and Alexander Wagner (University of Florida).

View abstract PDF

July 10, 19:00 ~ 19:25

Supervised Learning of Labeled Pointcloud Differences via Cover-Tree Entropy Reduction

Paul Bendich

Duke University, and Geometric Data Analytics, United States of America   -

We introduce a new algorithm, called CDER, for supervised machine learning that merges the multi-scale geometric properties of Cover Trees with the information-theoretic properties of entropy. CDER applies to a training set of labeled pointclouds embedded in a common Euclidean space. If typical pointclouds corresponding to distinct labels tend to differ at any scale in any sub-region, CDER can identify these differences in (typically) linear time, creating a set of distributional coordinates which act as a feature extraction mechanism for supervised learning. We describe theoretical properties and implementation details of CDER, and illustrate its benefits on several synthetic examples

Joint work with Abraham Smith (University of Wisconsin-Stout, Geometric Data Analytics), John Harer (Duke University, Geometric Data Analytics) and Jay Hineman (Geometric Data Analytics).

View abstract PDF

July 11, 14:30 ~ 14:55 - Room B7

Local cohomology and stratification

Vidit Nanda

The Alan Turing Institute and The University of Oxford, UK   -

I will outline an algorithm to recover the canonical (or, coarsest possible) stratification of a given regular CW complex into cohomology manifolds, each of which is a union of cells. The construction proceeds by iteratively localizing the poset of cells about a family of subposets; these subposets are in turn determined by a collection of cosheaves which capture variations in local cohomology across cells in the underlying complex. The result is a finite sequence of categories whose colimit recovers the canonical strata via isomorphism classes of its objects. The entire process is amenable to efficient distributed computation.

View abstract PDF

July 11, 15:00 ~ 15:25 - Room B7

Intrinsic $1$-dimensional persistence of geodesic spaces

Ziga Virk

IST Austria, Austria   -

Given a nice compact geodesic space $X$, such as a compact Riemannian manifold, we present the theory of intrinsic $1$-dimensional persistence, i.e., persistence on all points of $X$ induced by the geodesic distance. While the induced complexes have uncountably many vertices, the mentioned persistence turns out to be pretty tame and has very precise geometric interpretation. It also gives a specific understanding on how the size of holes is measured by persistence.

It turns out that persistence via Rips or Cech construction contains precisely the same information in both cases. This information represents the collection of lengths of the 'shortest' generating set. Furthermore, critical triangles can be used to localize minimal representatives of homology classes, and the approximation by finite samples is much more stable than suggested by standard stability theorems.

In the end we will outline how one may extract one-dimensional geometric information about $X$ from certain higher-dimensional persistence features.

View abstract PDF

July 11, 15:30 ~ 15:55 - Room B7

On the complexity of optimal homotopies

Arnaud de Mesmay

CNRS, Gipsa-lab, Université Grenoble-Alpes, France   -

We provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves $\gamma_1$ and $\gamma_2$ on a surface, we want to compute a homotopy between $\gamma_1$ and $\gamma_2$ where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very mathematical questions in quantitative homotopy theory to more practical applications such as similarity measures and graph searching problems.

Our main contribution is a structural theorem showing that there exist optimal homotopies which are very well behaved. It builds on earlier results in Riemannian geometry by Chambers and Liokumovitch and Chambers and Rotman. Leveraging on this theorem allows us to derive new exact and approximation algorithms to compute the homotopy height, and to draw connections with other problems in the same vein like homotopic Fréchet distance.

Joint work with Erin W. Chambers (Saint Louis University, USA), Gregory R. Chambers (Rice University, USA), Tim Ophelders (TU Eindhoven, Netherlands) and Regina Rotman (University of Toronto, Canada).

View abstract PDF

July 11, 16:00 ~ 16:25 - Room B7

Estimating the Reach of a Manifold

Frédéric Chazal

INRIA, France   -

Various problems in manifold estimation, and topological and geometric inference make use of the so-called the reach (also known as the conditioning number or feature size)which is a measure of the regularity of the manifold. In this talk, we will investigate into the problem of how to estimate the reach of a manifold M from point clouds randomly sampled on M. We propose an estimator of the reach (in the framework where the tangent spaces of M are known) and we obtain upper and lower bounds on the minimax rates for estimating the reach.

Joint work with E. Aamari (Inria and Université Paris-Saclay, France), J. Kim (Carnegie Mellon University, USA), B. Michel (Ecole Centrale de Nantes, France), A. Rinaldo (Carnegie Mellon University, USA) and L. Wasserman (Carnegie Mellon University, USA).

View abstract PDF

July 11, 17:00 ~ 17:25 - Room B7

Telling 3-manifolds apart: new algorithms to compute Turaev-Viro invariants

Jonathan Spreer

Freie Universität Berlin, Germany   -

The Turaev-Viro invariants are a powerful family of topological invariants. Although difficult to compute in general, they are the method of choice for computationally distinguishing between two given triangulations of 3-manifolds. I will discuss this family of invariants, and present an algorithm to compute them at level four, which runs in polynomial time for 3-manifolds with bounded first Betti number.

Joint work with Clément Maria (The University of Queensland, Brisbane, Australia).

View abstract PDF

July 11, 17:30 ~ 17:55 - Room B7

Embeddability in $\mathbb{R}^3$ is \textbf{NP}-hard

Eric Sedgwick

DePaul University, School of Computing, USA   -

Let $\textsc{Embed}_{k\rightarrow d}$ be the problem of deciding whether a given $k$-dimensional complex admits a piecewise-linear embedding in $\mathbb R^d$. The complexity of solving this problem varies widely in the parameters $k$ and $d$: \textsc{Graph Planarity} ($\textsc{Embed}_{1\rightarrow 2}$) is solvable in linear time, but in higher dimensions, depending on the codimension, the problem can range from polynomial-time solvable ($d \geq 4, k < (2d-2)/3$), to \textbf{NP}-hard ($d \geq 4, d \geq k \geq (2d-2)/3$), to undecidable ($k \geq d-1 \geq 4$).

We show that $\textsc{Embed}_{2\rightarrow 3}$ and $\textsc{Embed}_{3\rightarrow 3}$ are \textbf{NP}-hard, which helps to clarify the picture in dimension 3. These two problems were only recently shown to be decidable and, like that work, our proof relies heavily on the theory of 3-manifolds.

Joint work with Arnaud de Mesmay (CNRS, GIPSA-Lab, France), Yo'av Rieck (University of Arkansas, USA) and Martin Tancer (Charles University, Czech Republic).

View abstract PDF

July 11, 18:00 ~ 18:25 - Room B7

Random walks on groups with negative curvature

Joseph Maher

CUNY College of Staten Island, USA   -

We will discuss random walks on groups satisfying various types of negative curvature conditions. A simple example is the nearest neighbour random walk on the 4-valent tree, also known as the Cayley graph of the free group on two generators. A typical random walk moves away from the origin at linear speed, and converges to one of the ends of the tree. We will discuss how to generalize this result to more general settings, such as hyperbolic groups, or acylindrical groups.

Joint work with Giulio Tiozzo (University of Toronto).

View abstract PDF

July 12, 15:30 ~ 15:55 - Room B7

Deciding contractibility of a non-simple curve on the boundary of a 3-manifold

Éric Colin de Verdière

CNRS, LIGM, Université Paris-Est Marne-la-Vallée, France   -

We present an algorithm for the following problem: Given a triangulated 3-manifold $M$ and a (possibly non-simple) closed curve on the boundary of $M$, decide whether this curve is contractible in $M$. Our algorithm is combinatorial and runs in exponential time. This is the first algorithm that is specifically designed for this problem; its running time considerably improves upon the existing bounds implicit in the literature for the more general problem of contractibility of closed curves in a $3$-manifold. The proof of the correctness of the algorithm relies on methods of $3$-manifold topology and in particular on those used in the proof of the Loop Theorem.

Joint work with Salman Parsa (Mathematical Sciences Department, Sharif University of Technology, Tehran, Iran).

View abstract PDF

July 12, 16:00 ~ 16:25 - Room B7

Maximally persistent cycles in random geometric simplicial complexes

Matthew Kahle

Ohio State University, United States   -

One motivation for the emerging subject of stochastic topology is as a null hypothesis for topological statistics. There has been some earlier work studying the topology of random geometric simplicial complexes, but until recently not much was known about persistent homology of these complexes

In joint work with Omer Bobrowski and Primoz Skraba, we prove upper and lower bounds on the persistence of the maximally persistent cycle, agreeing up to a constant factor. The results hold for persistent $k$-cycles in $\mathbb{R}^d$, for all $d \ge 2$ and $2 \le k \le d-1$, and for both Vietoris–Rips and Cech filtrations. This is an important step in the direction of quantifying topological inference, separating topological signal from noise.

Joint work with Omer Bobrowski (Technion, Israel) and Primoz Skraba (Jozef Stefan Institute, Slovenia).

View abstract PDF

July 12, 17:00 ~ 17:25 - Room B7

Discrete uniformization for polyhedral surfaces and its convergence

Feng Luo

Rutgers University at New Brunswick, USA   -

We will discuss our work on discrete conformal geometry of polyhedral surfaces. A notion of discrete conformal equivalence of polyhedral surfaces is introduced and a discrete version of the uniformization theorem for compact polyhedral surfaces is established. We show that the discrete conformality is algorithmic and converges to the smooth conformal geometry. Applications to computer graphics will be addressed.

Joint work with David Gu, Jian Sun, and Tianqi Wu..

View abstract PDF

July 12, 17:30 ~ 17:55 - Room B7

Polyhedral realization of hyperbolic punctured spheres and discrete uniformization

Boris Springborn

Technische Universität Berlin, Germany   -

Two seemingly unrelated problems turn out to be equivalent. The first is a problem of 3-dimensional hyperbolic geometry: Given a complete hyperbolic surface of finite area that is homeomorphic to a sphere with punctures, find a realization as convex ideal polyhedron in hyperbolic space. The second is a problem of discrete complex analysis: Given a closed triangle mesh of genus zero, find a discretely conformally equivalent convex triangle mesh inscribed in a sphere. The existence and uniqueness of a solution of the first (hence also the second) problem was shown by I. Rivin. His proof is not constructive. A variational principle leads to a new constructive proof.

View abstract PDF

July 12, 18:00 ~ 18:25 - Room B7

Extrinsic Conformal Geometry Processing

Keenan Crane

Carnegie Mellon University, USA   -

This talk covers fundamental theory and algorithms for manipulating curved surfaces via conformal (i.e., angle-preserving) transformations. Conformal transformations are valuable in applications because they naturally preserve the integrity of geometric data. Until recently, however, there has been no theory of conformal transformations suitable for general-purpose geometry processing algorithms: previous methods for computing conformal maps have been purely intrinsic, with target domains restricted to the flat two-dimensional plane or other spaces of constant curvature. We instead consider a certain time-independent Dirac equation, which replaces the traditional Cauchy-Riemann equation for surfaces immersed in Euclidean 3-space. This equation leads to efficient numerical algorithms that enable processing of surface data via direct manipulation of extrinsic curvature. We will also discuss connections to the recent notion of discrete conformal equivalence based on length cross ratios, including recovery of shape from quantities like lengths and curvatures.

Joint work with Ulrich Pinkall (TU Berlin) and Peter Schröder (Caltech).

View abstract PDF



Visualising Normal Surfaces

Daniel Crane

University of Queensland, Australia   -

Many modern algorithms in computational topology rely on normal surfaces as a tool to study 3-manifolds. Despite their pivotal role in the study of 3-manifolds, little work towards visualising normal surfaces exists in the literature. To this end, we present a program that visualises triangulations of normal and almost normal surfaces. This is achieved by post processing force-directed layouts of the triangulations' layered primal/dual graphs. These can then be used to visualise 0-efficient triangulations of $S^3$, by tracking the normalisation of embedded almost normal spheres. An alternative – and aesthetically pleasing – visualisation method for normal spheres using Lombardi drawings is also explored.

View abstract PDF

The lexicographic degree of the first two-bridge knots

Pierre-Vincent Koseleff

UPMC - Sorbonne Universités (Paris 6), France   -

We study the degree of polynomial representations of knots. We give here the lexicographic degree of all two-bridge knots with 11 or fewer crossings. The proof uses the braid theoretical method developed by Orevkov to study real plane curves [BKP2], isotopies on trigonal space curves and explicit parametrizations obtained by perturbing a triple point.

The lexicographic degree of a knot $K$ is the minimal multidegree, for the lexicographic order, of a polynomial knot whose closure in $S_3$ is isotopic to $K$.

We show that this degree is not necessarily obtained for curves that have the minimal number of real crossings. For example the knot $8_6$ has minimal degree $(3,10,14)$ that corresponds to a diagram with 9 crossings while the alternating diagram with 8 crossings has degree at least $(3, 11, 13)$.

Here we study two-bridge knots, namely those that admit a trigonal parametrization, that is to say a polynomial parametrization in degree $(3,b,c)$. We show the sharp lower bound $c \geq 3N - b$, where $N$ is the crossing number of $K$.

Lower bounds for $b$ are obtained by considering first Bézout-like conditions on the real crossings of the plane projection.

We also use the associated 3-strings braid associated to any trigonal algebraic plane curve that must be quasi-positive [Or2].

Upper bounds are given by previous constructions on Chebyshev diagrams [KP3] and slide isotopies on knot diagrams : isotopies for which the number of crossings never increases [BKP1].

In addition, we introduce a new reduction $R$ on trigonal plane curves. In many cases, the use of this reduction allows to subtract three to the number of crossings of the diagram and to the degree $b$, thanks to a result on real pseudoholomorphic curves deduced from [Or2]. On the other hand we show that we can explicitly give a polynomial curve of degree $(3, d+3)$ from a polynomial curve of degree $(3, d)$ by adding a triple point and perturbing the singularity.

We obtain the lexicographic degree for some infinite familes of two-bridge knots (the torus knots and generalized twist-knots) and for all two-bridge knots with 11 or fewer crossings. For every considered knot, we compute first an upper bound $b_C$ for $b$, using Chebyshev diagrams. We compute all diagrams with $b_C -1$ or fewer crossings that cannot be reduced by slide isotopies. Most of these diagrams may be reduced using $R$-reductions. For those that cannot be reduced, we consider all possible schemes corresponding to admissible rational algebraic curve of degree $(3,b)<(3,b_C)$ and compute their associated braids, that must be quasi-positive.


[BKP1] E. Brugallé, P. -V. Koseleff, D. Pecker. Untangling trigonal diagrams, Journal Of Knot Theory And Its Ramificationsc (JKTR), 25(7) (2016), 10p.

[BKP2] E. Brugallé, P. -V. Koseleff, D. Pecker, On the lexicographic degree of two-bridge knots, Journal Of Knot Theory And Its Ramifications (JKTR), 25(7) (2016), 17p.

[KP3] P. -V. Koseleff, D. Pecker, Chebyshev diagrams for two-bridge knots, Geom. Dedicata 150 (2010), 405–425

[Or2] S. Yu. Orevkov. Classification of flexible $M$-curves of degree 8 up to isotopy, Geom. Funct. Anal., 12(4), 723–755, 2002.

Joint work with Erwan Brugallé (Centre de Mathématiques Laurent Schwartz, CMLA, École Polytechnique, France) and Daniel Pecker (UPMC - Sorbonne Universités, Paris 6, France).

View abstract PDF

String Topological Robotics II

My Ismail Mamouni

, Maroc   -

\begin{abstract} In a previous work, the authors claim to link two well known theories; namely the \textit{string topology} (founded by M. Chas and D. Sullivan in 1999) and the \textit{topological robotics} (founded by M. Farber some few years later, in 2003). For their purpose, their consider $G$ a compact Lie group acting transitively on a path connected $n$-manifold $X$. On the set $\MLP(X)$ of the so-called \textit{loop motion planning algorithms}, they define an \textit{string loop motion planning product} on the shifted string loop motion planning homology $\mathbb H_*(\MLP(X)) := H_{*+2n}(\MLP(X))$. In this talk, we finish this work and extend the graded commutative and associative algbera structure on $\mathbb H_*(\MLP(X)) $ to a structure of Gerstenhaber algebra and to that of Batalin-Vilkovisky algebra. \end{abstract}

\begin{thebibliography}{9} \bibitem[CS99]{CS} M. Chas, D. Sullivan, \textit{String Topology}, arXiv:math/9911159 [math.GT]. \bibitem[DM15]{DM1} Y. Derfoufi, M.I. Mamouni, \textit{Loop topologial complexity}, Bulletin to Computational Applied Mathematics, Vol. \textbf{3}, Vol.3, No.2 (2015), 31-36. \bibitem[DM16]{DM2} Y. Derfoufi, M.I. Mamouni, \textit{String topological robotics}, JP Journal of Geometry and Topology, Vol. \textbf{19}, Num. 3 (2016), 189-208. \end{thebibliography}

View abstract PDF

The Topology of $D$-stability

Grey Violet

University of Konstanz, Germany   -

The set of problems connected with $D$-stability: distribution of roots of a polynomial relative to a region $\Omega\subset{\mathbb C}$ is one of the fundamental in control theory, studied for such special cases as Hurwitz stability ($\Omega=\{Re z<0\}$) and Schur stability ($\Omega=\{|z|<1\}$) since the emergence of the field.

General theory of $D$-stability, which development could be attributed to R.E. Kalman, B.R. Barmish et al. gave different algorithmic and algebraic criteria for determining distributions roots of sets of polynomials in relation to $\Omega.$

Despite that the geometric information about the structure of spaces of polynomials with fixed distribution of roots is very limited.

Author describe topology of sets of polynomials or homogeneous binary forms with fixed number of roots inside $\Omega,$ on the border of $\Omega$ and outside of $\Omega$ using theory of symmetric products of topological spaces. Moreover author explains, the special position of 3 classical $D$-stability problems, namely, Hurwitz stability, Schur stability and hyperbolicity $\Omega=\mathbb R.$

View abstract PDF

FoCM 2017, based on a nodethirtythree design.