Scientific Program

Using points or small dots to represent any image or 2D shape is the most fundamental discrete representation derived from our geometric intuition. Point pattern synthesis involves generating such arrangements of points based on exemplars and is motivated by a variety of applications in computer graphics, including discrete texture generation, creative pattern design, object placement, scene creation, and distribution simplification. Building on recent advancements in statistical analysis and synthesis, we introduce computational tools to learn distributions from exemplars and seamlessly recreate them over larger areas.
Motivated by the interactive design of discrete textures, we also aim to develop near real-time methods to efficiently extract approximate statistical properties from an input pattern and replicate them within a larger domain. This can be motivated by applications, such as scene design for video games which require efficient (or even real-time) synthesis; for instance, to populate virtual worlds with diverse elements, from rocks to vegetation, either automatically or through interactive painting. Other applications are more sensitive to qualitative aspects of the synthesis from a spectral or statistical viewpoint. To address these, we will briefly revisit classical methodologies in point pattern analysis. Specifically, spectral analysis methods, such as the Fourier power spectrum and its radially averaged form, are commonly used to examine sample characteristics. In spatial analysis, the Pair Correlation Function (PCF) encodes pairwise distances between samples, through 1D or 2D histograms.
In this context, the data itself is highly varied. Some patterns have dominant anisotropic properties that are crucial to preserve. Others follow a structured arrangement, such as a grid or radial symmetry, which must be extended accordingly, often with multiple valid extensions. Shape distributions may be transformed into point patterns or handled directly using different representations (e.g., graphs, meshes, medial axes, simplified elements) and corresponding shape-aware metrics. In addition to introducing a novel proximity formulation between distribution elements based on statistical features, we show how sharp variations in density and correlation are handled using an adapted bilateral filtering setting. Among the many challenging criteria for point pattern synthesis techniques, we will focus on multi-class and multi-attribute distribution handling, anisotropic and structured pattern replication, and shape-aware metrics. This research collection leads us to a computational framework for fast, user-friendly point pattern editing, providing a link to image processing tools through a low-dimensional perceptual embedding for point correlations. Each pattern is mapped to a three-channel feature image that can be manipulated with standard image software. Applications such as material appearance, haptic rendering, smart-city design, and reforestation can benefit from this first interactive editing framework for point patterns.

We address in this talk the problem of curvature estimation for surfaces in R³ from points and normals and introduce to this purpose the notion of corrected curvature measures. Curvature measures were originally introduced by Herbert Federer in 1958 for sets of positive reach and extended in 1994 by Joseph Fu to a larger class of geometrics objects containing subanalytics sets, digitized objects and triangulations. The construction of these measures is based on the notion of normal cycle and they have been shown to be stable in different settings, for instance by Cohen-Steiner and Morvan in 2003, when the normals to the shape can be well approximated. In this talk, we will extend the notion of normal cycle of a surface S to a couple (S,u), where u is any unit vector field on S. The idea is to replace in the construction of the normal cycle the geometric unit normal field by any vector field u. This naturally gives a new definition of curvature measures of S, that we call corrected curvature measures. We will see that the curvature measures of C² surfaces can be well approximated by corrected curvature measures of approximations, even though their geometric normals are noisy. We will illustrate on several examples that this provides a simple and stable tool for curvature estimation. This is a joint work with David Coeurjolly, Céline Labart, Jacques-Olivier Lachaud and Pascal Romon.

Union volume estimation is a classical geometric problem. Given a family of objects in d-dimensional Euclidean space, we want to approximate the volume of their union. In the special case where all objects are hyperrectangles this is known as Klee's measure problem.
The state-of-the-art algorithm [Karp, Luby, Madras '89] for union volume estimation as well as Klee's measure problem in constant dimension d computes a (1+epsilon)-approximation with constant success probability by using a total of O(n/epsilon²) queries of the form (i) ask for the volume of an object, (ii) sample a point uniformly at random from an object, and (iii) query whether a given point is contained in an object.
In this talk we will discuss two results. First, we show that if one can only interact with the objects via the aforementioned three queries, the query complexity of [Karp, Luby, Madras '89] is indeed optimal.
Second, guided by the insights of the lower bound, we provide a more efficient approximation algorithm for Klee's measure problem.

In the realm of 3D-computer vision applications, point cloud few-shot learning plays a critical role. However, it poses an arduous challenge due to the sparsity, irregularity, and unordered nature of the data. Current methods rely on complex local geometric extraction techniques such as convolution, graph, and attention mechanisms, along with extensive data-driven pre-training tasks. These approaches contradict the fundamental goal of few-shot learning, which is to facilitate efficient learning. To address this issue, we propose GPr-Net (Geometric Prototypical Network), a lightweight and computationally efficient geometric prototypical network that captures the intrinsic topology of point clouds and achieves superior performance.

We consider clustering problems that are fundamental when dealing with trajectory and time series data. The Fréchet distance provides a natural way to measure similarity of curves under continuous reparametrizations. Applied to trajectories and time series, it has proven to be very versatile as it allows local non-linear deformations in time and space. Subtrajectory clustering is a variant of the trajectory clustering problem, where the start and endpoints of trajectory patterns within the collected trajectory data are not known in advance. We study this problem in the form of a set cover problem for a given polygonal curve: find the smallest number k of representative curves such that any point on the input curve is contained in a subcurve that has Fréchet distance at most a given r to a representative curve.

The shapes that appear in discrete images are described by discrete coordinates. In general, their topological and geometric properties differ from those of their continuous counterparts. The aim of this presentation is to identify a family of continuous shapes that is sufficiently restricted so that their discrete equivalents preserve certain topological properties, yet broad enough to include both certain polygons and regular shapes.

Deployable surfaces are surfaces that are fabricated flat and assume a 3D shape upon internal or external forces. Their final shape can be characterized by the local deformation from the 2D to 3D state, in particular the local change of metric and the curvature of the surface. In this talk, I will present some recent work that shows how we can program these properties so as to obtain a deployable surface that approximates a given target shape once deformed. We assume the structure of our deployable can be defined by quasi-periodic parametric patches whose parameters smoothly vary over the surface and we propose a two-scale approach where we first pre-compute the map between design parameters and patch deformation and then grade the patches to obtain the final structure. I will show applications to the design of 3D inflatable shells and freeform surfaces made by printing ribbons on stretched fabric.

In a seminal paper Henry Whitehead introduced four elementary operators, collapses and expansions (the inverse of a collapse), perforations and fillings (the inverse of a perforation), which correspond to an homotopy equivalence between two simplicial complexes. In this talk, we consider some transformations which are obtained by the means of these four operators. The presentation is composed of two parts. We begin the first part by introducing a certain axiomatic approach for combinatorial topology, which is settled in the framework of completions. Completions are inductive properties which may be expressed in a declarative way and may be combined. Then, we present a transformation that is based solely on collapses and expansions. This transformation involves homotopic pairs, it may be seen as a refinement of simple homotopy, which takes as input a single object. A homotopic pair is a couple of objects (X, Y ) such that X is included in Y and (X, Y ) may be transformed to a trivial couple by collapses and expansions that keep X inside Y . Our main result states that the collection of all homotopic pairs may be fully described by four completions which correspond to four global properties. After, we consider a transformation that is based on collapses, expansions, perforations, and fillings. This transformation involves contractible pairs, which are extensions of homotopic pairs. Again we show that the collection of all contractible pairs may be fully described by four completions which correspond to four global properties. Three of these completions are the same as the ones describing homotopic pairs. In the second part of the presentation, we introduce the notion of a Morse sequence, which provides a very simple approach to discrete Morse theory. A Morse sequence is obtained by considering only expansions and fillings of a simplicial complex; or, in a dual manner, by considering only collapses and perforations. A Morse sequence may be seen as an alternative way to represent the gradient vector field of an arbitrary discrete Morse function. We introduce reference maps, which are maps that associate a set of critical simplexes to each simplex appearing in a Morse sequence. By considering the boundary of each critical simplex, we obtain a chain complex from these maps, which corresponds precisely to the Morse complex. Then, we define extension maps. We show that, when restricted to homology, an extension map is the inverse of a reference map. Also we show that these two maps allow us to recover directly the isomorphism theorem between the homology of an object and the homology of its Morse complex

Polytopal sphere packings are a family of sphere packings that carry a combinatorial structure defined by an edge-scribable polytope. This feature allows us to define a dual structure, analogous to the duality of planar graphs, for the volumetric meshes produced by the skeletons of these packings. In this talk, we will explore how these objects can be used to extend classic subdivision methods for polygon meshes to volumetric meshes, and to model tubular surfaces and lacunary structures in 2D and 3D.
Based on joint works with Boris Bordeaux, Christian Gentil, and Jorge Ramírez Alfonsín.

Attribute Profiles (APs) were originally defined as sequences of filtering operators on inclusion trees, i.e., the max- and min-trees, from the input image. In this presentation, the AP paradigm will be extended to the framework of hierarchical watersheds, where the semantic knowledge provided by labeled training pixels is explored during different phases of the watershed-AP construction: within the construction of hierarchical watersheds and later within the filtering of the resulting hierarchy. Two applications of the proposed method will be illustrated, including land cover classification and building extraction, using optical remote sensing images.

Given a finite set of points P that sample an unknown smooth surface M ⊆ R³, we aim to approximate M based solely on P. This problem, known as surface reconstruction, has been a common research focus in computer graphics and computational geometry. Many algorithms have been proposed to solve it and some come with theoretical guarantees. The most desirable guarantee is that the reconstuction output is homeomorphic to M, in which case we call the algorithm topologically correct. In this talk, we present a simple algorithm, Naive Squash, that outputs the result of simplifying the α-complex of P by repeatedly applying a new type of collapse, termed vertical relative to M. Naive Squash has a practical version that does not rely on the knowledge of M. We formulate general conditions under which the Squash algorithms (in both naive and practical forms) are topologically correct, when M is a smooth orientable submanifold in R^d with codimension one. Providing a bound when d = 3 on the angle that triangles in the α-complex make with M, we obtain—for the particular case of a smooth surface embedded in R³—sampling conditions on P that are competitive with the existing ones in the literature.
This is a joint work with Mattéo Clémot, Bianca Dornelas and André Lieutier.

Engineering analysis should match an underlying designed shape and not restrict the quality of the shape. I.e. one would like finite elements matching the geometric space optimized for generically good shape. Since the 1980s, classic tensor-product splines have been used both to define good shape geometry and analysis functions (finite elements) on the geometry.
Polyhedral-net splines (PnS) generalize tensor-product splines by allowing additional control net patterns required for free-form surfaces: isotropic patterns, such as n quads surrounding a vertex, an n-gon surrounded by quads, polar configurations where many triangles join; and preferred direction patterns, that adjust parameter line density, such as T-junctions. PnS2 generalize C1 bi-2 splines, generate C1 surfaces and can be output bi-3 Bezier pieces. There are two instances of PnS2 in the public domain: a Blender add-on and a ToMS distribution with output in several formats. PnS3 generalize C2 bi-3 splines for high-end design.
PnS generalize the use of higher-order isoparametric approach from tensor-product splines. A web interface offers solving elliptic PDEs on PnS2 surfaces and using PnS2 finite elements.

Differential geometry is extensively used in physics to study the behaviour of 3D spaces. Studying differential (or local) structure of a surface under a deformation helps to express local constraints that can be exploited to solve key computer vision problems such as 3D reconstruction, registration or any kind of manipulation. I will discuss what are the benefits of the 'local' approaches over the 'global' ones, the challenges and what does the future look like for the 'local' methods.

Topological Data Analysis (TDA) is based on the concept of interpreting datasets as geometric objects that can be analyzed using tools from algebraic topology. For a point cloud data, a filtration of topological spaces can be constructed as a multiscale approximation of the underlying space from which the data is assumed to be sampled. The dataset's geometry is then captured through topological invariants of the filtration, such as persistent homology, which remains stable under data perturbations.
Recent advances in data collection in fields like cancer biology, geospatial analysis, and ecology have resulted in chromatic (labeled) data, where interactions between points of different labels are of interest. In these scenarios, it is important to understand not only the spatial relationships within the entire dataset but also among subsets defined by these labels. The chromatic alpha filtration [Mon+24] generalizes the alpha filtration to capture these spatial relationships among labeled point clouds and has applications in TDA for multi-species data. We introduce the chromatic Delaunay–Čech and chromatic Delaunay–Rips filtrations, which are computationally more efficient alternatives to the chromatic alpha filtration. Using generalized discrete Morse theory, we demonstrate that the Čech, chromatic Delaunay–Čech, and chromatic alpha filtrations are related through simplicial collapses. This generalizes Bauer and Edelsbrunner’s result from the non-chromatic to the chromatic setting and justifies the use of more cost-effective filtrations for the analysis of chromatic data.
[Mon+24] di Montesano, S. Cultrera, et al. "Chromatic alpha complexes." arXiv preprint arXiv:2212.03128 7 (2024).
Joint work with Abhinav Natarajan, Thomas Chaplin, Adam Brown.

Directional and vector fields are the centerpiece of classical smooth differential geometry. As such, they have been extensively studied in discrete differential geometry and the finite-element literature. However, their many flavors of discretization and representation still pose challenges. I will discuss the requirements from such fields and recent solutions. This includes sampling quality, structure preservation, higher-order generalization, and topology analysis and control both in 2D and in 3D.

In this talk, we will present results on two seemingly unrelated problems: the first problem is to find quasi-geodesics on polyhedral spheres and the second problem is to find knots for which any possible diagram has high (tree-)width. I will explain why both questions boil down to understanding the best way to sweep a sphere using lower-dimensional spheres and conclude by highlighting some algorithmic open problems on this theme.
Based on joint works with Jean Chartier, Corentin Lunel, Jessica Purcell, Saul Schleimer and Eric Sedgwick.

We propose a natural framework for the study of surfaces and their different discretizations based on varifolds. Varifolds have been introduced by Almgren to carry out the study of minimal surfaces. Though mainly used in the context of rectifiable sets, they turn out to be well suited to the study of discrete type objects as well. While the structure of varifold is flexible enough to adapt to both regular and discrete objects, it allows to define variational notions of mean curvature and second fundamental form based on the divergence theorem. Thanks to a regularization of these weak formulations, we propose a notion of discrete curvature (actually a family of discrete curvatures associated with a regularization scale) relying only on the varifold structure. We performed numerical computations of mean curvature and Gaussian curvature on 3D point clouds to illustrate this approach. Though flexible, varifolds require the knowledge of the dimension of the shape to be considered. By interpreting the product of the Principal Component Analysis, that is the covariance matrix, as a sequence of nested subspaces naturally coming with weights according to the level of approximation they provide, we are able to embed all d-dimensional Grassmannians into a stratified space of covariance matrices. Building upon the proposed embedding of Grassmannians into the space of covariance matrices, we generalize the concept of varifolds to what we call flagfolds in order to model multi-dimensional shapes.

The software ecosystem for geometric data analysis is evolving quickly. Modern libraries such as PyTorch, PyVista or Taichi open exciting research directions, but also challenge the long-term viability of our research projects: as major libraries get deprecated from one year to the next, how can we build software that is both cutting edge and future-proof? In this presentation, I will discuss the main tradeoffs involved in those decisions, and share some practical tips learnt through the development of the KeOps, GeomLoss and scikit-shapes libraries.

Computational geometry is the area within algorithms research that deals with the design and analysis of algorithms and data structures for spatial data. In this talk I will present a variety of results which highlight the use of techniques from computational geometry and computational topology in three different application areas: geomorphology, wildlife ecology, and meshing. Specifically, I will first discuss algorithms to extract meaningful networks from braided river systems and estuaries based on sediment volume and then show how we intend to track these networks over time in the Western Scheldt and Wadden Sea. Then I will describe an approach to characterize and track the shape of herds of animals based on density surfaces. Finally, I will briefly touch upon our latest results on creating valid polycube layouts for conformal mesh generation for aerospace models.

This talk will present a computational framework for the Principal Geodesic Analysis of merge trees (MT-PGA), a novel adaptation of the celebrated Principal Component Analysis (PCA) framework to the Wasserstein metric space of merge trees. We formulate MT-PGA computation as a constrained optimization problem, aiming at adjusting a basis of orthogonal geodesic axes, while minimizing a fitting energy. We introduce an efficient, iterative algorithm which exploits shared-memory parallelism, as well as an analytic expression of the fitting energy gradient, to ensure fast iterations. Our approach also trivially extends to persistence diagrams. Extensive experiments on public ensembles demonstrate the efficiency of our approach - with MT-PGA computations in the orders of minutes for the largest examples. We show the utility of our contributions by extending to merge trees two typical PCA applications. First, we apply MT-PGA to data reduction and reliably compress merge trees by concisely representing them by their first coordinates in the MT-PGA basis. Second, we present a dimensionality reduction framework exploiting the first two directions of the MT-PGA basis to generate two-dimensional layouts of the ensemble. We augment these layouts with persistence correlation views, enabling global and local visual inspections of the feature variability in the ensemble. In both applications, quantitative experiments assess the relevance of our framework. Finally, we provide a C++ implementation that can be used to reproduce our results.

I will introduce proxys for the distance function to the support of a measure, which sublevel sets are unions of balls of unions of ellipsoids. I will provide results about rates of approximation for these proxys by their empirical version. I will explain how to use such estimators for clustering data with a specific shape. The results are extracted from the papers [1,2] and from works in progress.
[1] C. Brécheteau. Robust anisotropic power-functions-based filtrations for clustering. In 36th International Symposium on Computational Geometry (SoCG 2020), vol. 164, 2020.
[2] C. Brécheteau, C. Levrard. A k-points-based distance for robust geometric inference. Bernoulli, 26(4), 2020.

The presentation aims to provide a subjective account of the unfinished history of Discrete Tomography, from its origins to some of its open problems including some of its most interesting results

• GT GeoAlg -- computational geometry
• GT GDMM -- digital geometry and mathematical morphology
• GT MG -- geometric modeling

Manifold reconstruction aim is to compute a triangulation of a manifold given a (dense enough) sample of it. Because of its practical impact in the industry, this problem has given rise to a large amount of literature in several fields, including geometry processing, geometric modeling, and computer aided design.
In this talk, we focus on homological oriented approaches, where the triangulation is obtained as a minimal simplicial chain under boundary constraints. We will consider in particular L¹ and lexicographic minima. For both settings we give some geometric properties and    describe algorithms for their computations. In particular, the algorithms for lexicographic minimisation is strongly related to the matrix reduction used for the computation of persistent homology of a simplicial filtration. In order to address a large audience, we will first provide and explain the minimal required definitions in simplicial homology.

Inspired by the strengths of quadric error metrics initially designed for mesh decimation, we devised a concise mesh reconstruction approach for 3D point clouds. Our approach proceeds by clustering the input points enriched with quadric error metrics, where the generator of each cluster is the optimal 3D point for the sum of its quadric error metrics. This approach favors the placement of generators on sharp features, and tends to equidistribute the error among clusters.
I will also present a novel learnable mesh representation through a set of local 3D sample points and their associated normals and quadric error metrics w.r.t. the underlying shape. A global mesh is directly derived by efficiently leveraging the knowledge of the local quadric errors. We guarantee both topological and geometrical properties by ensuring that the output mesh does not self-intersect and is always the boundary of a volume.

(TBA)