Planning

Modern imaging technologies provide complex and geometrically rich biological/geological/astrological/... data. Extracting relevant information from this data is a major challenge for understanding the underlying phenomena. In this context, topological integral transforms, introduced in algebraic geometry in the late 1980s by P. Schapira and O. Viro, are currently experiencing a remarkable resurgence. Just as the Fourier transform provides a relevant representation of a digital signal, these integral transforms extract geometric information from shapes using a topological integration technique, with the Euler characteristic as a measure. Importantly, these transforms satisfy an inversion theorem, ensuring the preservation of the initial geometric information, which motivates their practical use. During these two talks, I will present the theory of integration with respect to the Euler characteristic, the associated integral transforms, and their numerical implementations. Finally, I will present recent applications in the biological and medical fields.

We have a flat square box, and our goal is to place the largest possible number of oranges in it in a single layer. The solution to this problem is known only for boxes whose side does not exceed six times the diameter of an orange. In most cases, a computer is needed to find it. However, if the box is infinite (i.e., the entire plane), the optimal arrangement is easily obtained. Now let's consider the analogous problem in three dimensions: we want to stack oranges as compactly as possible in space. Kepler conjectured that the 'cannonball' packing is optimal. It took 400 years for this conjecture to be proven by Hales and Ferguson, whose proof consists of 250 pages of text and tens of thousands of lines of code. What happens if we want to store both oranges and clementines?

A polyhedral surface or a flat surface with conical singularities is a surface obtained by gluing edges of polygons in the Euclidean plane by orientable isometries (that is rotations and translations). From its definition, a polyhedral surface inherits a metric that allows to measure distances and areas. A polyhedral surface can be more intrinsically defined, that is without a reference to a polygonal decomposition, by defining directly the metric as a flat metric with conical singularities. A typical example of a polyhedral surface is the boundary of a 3-dimensional (non-necessarily convex) polytope in the 3-dimensional Euclidean space. Polyhedral surfaces also appear in the study of polygonal billiards and in the geometry of surfaces.

In these lectures we first review some basis on the topology of surfaces, embedded graphs and related computational problems. Then we turn to the geometric notion of polyhedral surfaces and how they can be encoded in different computational models (RAM or real RAM). Next, we consider two main classes of algorithmic problems: the study of straight line segments and distances and the problem of embedding isometrically a polyhedral surface in 3-space. Two ubiquitous tools in the course are first the notion of (weighted) Delaunay triangulation of a polyhedral surface which provide a canonical triangulation of polyhedral surfaces and the moduli space of polyhedral surfaces which parametrize up to isometries the set of polyhedral surfaces with fixed combinatorics.

Topological Data Analysis (TDA) aims to reveal and leverage the topological and geometric structures of complex, often high-dimensional data.

TDA relies on well-founded mathematical theories and computational tools that can be used either independently or in combination with other data analysis and statistical learning techniques.

The first part of this talk will be a (very) short reminder on TDA, after which I will give a partial survey of statistical results in this area.

In the second part of the talk, I will present selected results in greater detail, including proofs.

Dans cette première partie, on définira ce qu’est l’arrangement d’une famille de courbes algébriques planes et on énoncéra le résultat de complexité qui sera exposé et qui améliore significativement les résultats précédents de Kerber. Puis on décrira deux sous-alogrithmes qui jouent un rôle cléf dans le résultat final.

Basé sur un article en préparation de Daouda Niang Diatta, Sény Diatta et Marie-Françoise Roy

Dans cette deuxième partie, on présentera l’algorithme de calcul de l’arrangement d’une famille de courbes algébriques planes. La méthode sera illustrée par un exemple détaillé permettant de voir tous les phénomènes qui peuvent survenir dans le cas algébrique, et qui n’apparaissent pas dans le cas linéaire.

Basé sur un article en préparation de Daouda Niang Diatta, Sény Diatta et Marie-Françoise Roy

Consider f a polynomial in x and t with complex coefficients. The set of complex roots of f in x when t moves continuously along a loop in the complex plane defines a braid, provided that t avoids a certain set of critical values. Artin proved that braids can be described as a finite concatenation of elementary generators, and our goal is to compute such a decomposition for the braid induced by the displacement of the roots of f. Starting with the algebraic input f, we first numerically track its roots using certified homotopy continuation. This procedure outputs disjoint tubular neighborhoods, each containing a strand of the induced braid. Although this output is by nature numerical, we can recover the braid expressed in terms of Artin's generators from it. This discrete description is certified, even though the intermediate step involves numerical computations. We provide a Rust implementation of the second step that can be piped with Algpath, a certified path tracking software, allowing for certified braid monodromy computations.

We study the problem of answering connectivity queries on real solution sets of polynomial systems, a central question with applications from geometry to robotics. Following Canny’s roadmap framework, such queries on a high-dimensional solution set are reduced to connectivity queries on a one-dimensional curve intersecting all components. We present an algorithm that, under generic assumptions, computes roadmaps in subquadratic time with respect to the output size, thereby extending the best known, nearly optimal complexity bounds to unbounded cases. Finally, we illustrate the applicability of our approach through a prototype implementation to analyze the singularities of a PUMA-type robot, building on recent advances in Gröbner basis computations. This is joint work with M. Safey El Din and É. Schost.

Let P be a finite full-dimensional point configuration in \(\mathbb{R}^d\). We show that if a point configuration Q has the property that all finite chirotopes realizable by adding (generic) points to P are also realizable by adding points to Q, then P and Q are equal up to a direct affine transform. We also show that for any point configuration P and any \(\varepsilon > 0\), there is a finite, (generic) extension \(\widehat{P}\) of P with the following property: if another realization Q of the chirotope of P can be extended so as to realize the chirotope of \(\widehat{P}\), then there exists a direct affine transform that maps each point of Q within distance \(\varepsilon\) of the corresponding point of P.

Self-supervised learning (SSL) has emerged as a powerful paradigm for learning representations without labeled data, often by enforcing invariance to input transformations such as rotations or blurring. Recent studies have highlighted two pivotal properties of effective representations: (i) avoiding dimensional collapse—where the learned features occupy only a low-dimensional subspace—and (ii) promoting uniformity in the induced distribution.

In this talk, I will present T-REGS, a simple regularization framework for SSL based on the length of the Minimum Spanning Tree (or, equivalently, the total persistence in degree 0 of the Rips filtration) over the learned representations. I will discuss theoretical analysis demonstrating that T-REGS simultaneously mitigates dimensional collapse and enhances distribution uniformity on arbitrary compact Riemannian manifolds. Finally, I will show empirical results on synthetic data and standard SSL benchmarks, illustrating how T-REGS improves representation quality in practice.

Recent developments in the Multiparameter topological persistence theory has enabled the efficient computation of several new TDA invariants, allowing us to capture richer geometrical and topological features in complex datasets.

In this talk, I will present several strategies for integrating multipersistence invariants and their estimations into machine learning workflows. I will discuss their geometrical and statistical approximation guarantees, including explicit tight upper bounds and convergence rates.

To understand the geometry of a graph G embedded on a closed surface, an interesting tool is the number of intersection of G with any closed curve c. A useful map is the length spectrum \(\mu_G(c)\) counting the minimum number of intersections between G and any curve freely homotopic to c. The notion of kernel have been introduced by Schrijver in the 90’s. It corresponds to an embedded graph G such that for any proper minor H of G \(\mu_H < \mu_G\). It is quite obvious that any embedded graph G has a minor K which is a kernel and with same length spectrum. Such a minor is called a minor kernel. In this talk, I describe an algorithm to compute a minor kernel of a given graph in polynomial time. Thanks to a correspondence with system of curves, this algorithm relies on a tight bound on the length of minimal bigon in system of curves. This is a joint work with my PhD supervisors Vincent Delecroix and Francis Lazarus.

Let \(f \colon G \to H\) be a graph homomorphism. In general, \(f\) is not injective; the goal is to transform \(f\) into an embedding by introducing a new dimension, that is, replacing H with \(|H| \times \mathbb{R}\) and perturbing \(f\) along \(\mathbb{R}\). In this setting, this problem is connected to other questions in topology and topological graph theory. In particular, when H is a path graph, it is known as the level planarity problem. We introduce a new framework for studying liftings when G is a tree and H is a path graph. Using it, we establish a simple criterion for liftability, inspired by the van Kampen obstruction, and give a new algorithm for constructing liftings.

In this work, we introduce and study what we believe is an intriguing and, to the best of our knowledge, previously unknown connection between two fundamental areas in computational topology, namely topological data analysis (TDA) and knot theory. Given a function from a topological space to \(\mathbb{R}\), TDA provides tools to study the simplify and study the importance topological features: in particular, the \(l\)-th dimensional persistence diagram encodes the topological changes (or \(l\)-homology) in the sublevel set as the function value increases into a set of points in the plane. Given a continuous one parameter family of such functions, we can combine the persistence diagrams into an object known as a vineyard, which track the evolution of points in the persistence diagram as the function changes. If we further restrict that family of functions to be periodic, we identify the two ends of the vineyard, yielding a closed vineyard. This allows the study of monodromy, which in this context means that following the family of functions for a period permutes the set of points in a non-trivial way. Recent work has studied monodromy in the directional persistent homology transform, demonstrating some interesting connections between an input shape and monodromy in the persistent homology transform for 0-dimensional homology embedded in \(\mathbb{R}^2\).

In this work, given a link and a value \(l\), we construct a topological space (based on the given link) and period family of functions on this space (based on the Euclidean distance function), such that the closed \(l\)-vineyard contains this link. This shows that vineyards are topologically as rich as one could possibly hope, suggesting many future directions of work. Importantly, it has at least two immediate consequences we explicitly point out:

• Monodromy of any periodicity can occur in a \(l\)-vineyard for any \(l\). This answers a variant of a question by Arya and collaborators. To exhibit this as a consequence of our first main result we also reformulate monodromy in a more geometric way, which may be of interest in itself.
• Topologically distinguishing closed vineyards is likely to be difficult (from a complexity theoretical as well as a perspective) because of the difficulty of knot and link recognition, which have strong connections to many NP-Hard problems.

A hyperbolic surface can be viewed as a Riemannian surface of constant curvature -1. Meanwhile, the incremental Bowyer-Watson algorithm is a classical method for computing Delaunay triangulations of point sets in the Euclidean plane. The goal of this talk is to extend this algorithm to the case of hyperbolic surfaces. After a brief review of the Bowyer-Watson algorithm, we will introduce the notion of Delaunay triangulation on hyperbolic surfaces, and then present how the Bowyer-Watson algorithm can be adapted to this setting.