Seminar of Departement 1 at LORIA

Seminar of Departement Algorithms, Computation, Image and Geometry at LORIA

This page presents seminars of the department Algorithms, Computation, Image and Geometry together with more specialized team seminars from teams ABC, Adagio, Caramba, Gamble, Tangram, MFX, and Pixel.

2024

Day of the Department / Journée des doctorants du département

28 juin 2024, salle A008

Camille Lanuel. Gamble. Computing an epsilon-net on a hyperbolic surface
An epsilon-net of a metric space is a set of points such that the balls of radius epsilon centered at those points cover the space, and two distinct points of the epsilon-net are at least epsilon apart. Hyperbolic surfaces are surfaces that are locally isometric to the hyperbolic plane. There is not a lot of algorithmic tools to handle them, so we want to compute epsilon-nets on them. This will open the door to approximation algorithms on hyperbolic surfaces and help to study them. In my presentation, I will explain what is a hyperbolic surface and how we can compute epsilon-nets on it using a Delaunay refinement algorithm.

Nicolas Maignan. Tangram. Studies and challenges in legacy video colorization
Video colorization gives a new look to archival documents, making them more attractive among new generations. This work not only requires in-depth research to ensure historical accuracy, but is also time-consuming due to the processing of the thousands of images making up a video sequence. Current methods aimed at streamlining this process remain inefficient, with significant variations in hue over time, incomplete results for automatic methods, and artifacts appearing during frame-by-frame colorization. Despite reduced computation times, these shortcomings persist, forcing professionals to rework sequences manually, even after using algorithms guided by already colorized frames. Moreover, there is no database of old video in color, so the ground truth is not available to train a classical big data model.
The aim of this thesis is to develop colorization methods that are more stable over time, enabling experts to produce results with the desired hues and saturations and low data consuming. The first method we propose is based on a neural network using spatial and temporal convolution kernels to diffuse the colors from a few frames to the rest of the video. This first approach is fully unsupervised and does not require any database. The aim of this approach is to guarantee consistent colorization faithful to the user's style. In a second step, we studied the limitations of the well-known DeOldify method to check if this approach is accurate with a few amounts of data and with Technicolor movie, aiming to use similarly contrasted video.

Sarah Wajsbrot. Gamble. Robust optimization through a geometric lens
How to deal with uncertain data in an optimization problem? Uncertainty may come from (i) measurement or estimation errors of physical and environmental parameters, or unpredictable agent behaviors and also from (ii) implementation errors for computational reasons. Robust optimization is a methodology to obtain solutions that are worst-case optimal i.e. resistant to any outcome of the uncertain data. We study an instance of two-stage robust linear program: here we are allowed to take some decisions once the uncertainty is revealed. Though it is known to be a hard problem, it can be approximated by a "k-adaptability" version: before revealing uncertainty, preselect k decisions and choose the best after uncertainty is revealed. Is the latter tractable, what is the geometry of its feasible region, and can we use tools from combinatorial convexity to understand better these problems?

Marie Bolzer. Caramba. Lightweight implementations of S-boxes in symmetric cryptography.
Cryptography aims to secure connections, data and, more generally, information systems. However, cryptography adds a significant cost to system and network infrastructures. Two major issues stand out, reducing costs as much as possible and obtaining and verifying security. The aim of my thesis is to use algorithms and develop tools to make progress on these issues. I will focus on S-boxes which are non-linear cryptographic components. There are omnipresent in standard block cipher constructions used in symmetric cryptography. How to optimize its implementation, depending on context and technology, is therefore an important issue.

Hugo Leblond. Tangram. Study of implicit and hybrid representations for Simultaneous Localization And Mapping (SLAM) with LiDAR.
This thesis explores the application of implicit and hybrid representations in simultaneous localization and mapping (SLAM) using LiDAR technology. The presentation begins with a review of the state of the art and a comparison between Neural Radiance Fields (NeRFs) and Gaussian Splatting. Gaussian Splatting will then be studied in greater depth, chosen for its precise environmental rendering capabilities and memory efficiency. The presentation will then propose directions for ongoing work aimed at overcoming the limitations of current methods, improving accuracy, computational efficiency and management of large, complex environments.

Julien Soumier. Caramba. Going in higher dimensions to break and create isogeny based protocols.
A cornerstone of modern cryptography is the Diffie-Hellman algorithm, which allows two parties to safely agree on a shared key. It is based on the discrete logarithm problem. This protocol was considered very secure until the advent of quantum algorithms. However, with the potential release of quantum computers, we need to develop new key exchange protocols. One candidate to resist quantum attacks is isogeny-based cryptography. I will present the basics of this theory and explain why current research is exploring higher-dimensional isogenies.

Medhi Kermaoui. Caramba. Isogeny-based cryptography.
In 1994, Peter Shor designed a quantum algorithm for efficiently factoring large numbers and solving the discrete logarithm problem, two fundamental problems on which public-key cryptography is based. In light of this threat, the field of post-quantum cryptography has emerged, aiming to develop cryptographic techniques that are secure against quantum attacks. Isogeny-based cryptography is one of the candidates for quantum-resistant cryptography.

MFX Seminar

3 April, 10:30 C103
Eric Garner TU Delft
Computational design of patient-specific implants: from micro-architected materials to shape-matching geometry
Despite over a century's worth of technical improvements, the long-term survivability associated with orthopedic implants continues to fall short. In contrast to earlier designs, implant failure is no longer caused by a structural failure of the implant itself. Rather, it results from the plant's long-term deleterious effects on the surrounding bone tissue. Over time, changes in mechanical loading conditions induce a reduction in bone density, increasing the risk of fracture and destabilizing the bone-implant interface. The mechanisms which drive peri-prosthetic bone loss are complicated and inter-related. Add to this the unique morphological variations between patients, and an optimal one-size-fits-all solution seems unlikely. This research aimed to develop computational design strategies that automatically generate patient-specific implants based on medical imaging, in an effort to improve their long-term survivability.

PIXEL Seminar

15 March, 10:00 A006
Bernhard Kerbl TU Wien
Compute-Based Rendering across the Board: Efficient Methods for Meshes, Point Clouds and Radiance Fields
Dr. Kerbl will present his on-going research on compute-based rendering and its use across 3D representations and applications. Modern 3D content, both synthetic and captured, contains an unprecedented amount of geometric detail. At the same time, user appreciation of 3D content demands low-latency feedback loops: processing, exploring or modifying 3D scenes should be fast, or---even better---instant. Failure to meet performance targets is often answered by applying more raw compute power to the problem. This policy has led to systematic hardware hoarding, a rift between "GPU-rich" and "GPU-poor", increased reliance on cloud computing and an overall rise in global resource consumption. A more sustainable solution to this challenge lies in the careful design of inherently parallel algorithms, finding novel data structures and optimal 3D scene representations for specific tasks. One pillar of the research by Dr. Kerbl et al. towards this goal is the use of compute-based rendering: exploiting GPU compute to assist or replace the fixed-function pipeline for image formation. This talk illustrates concrete examples where compute-based rendering achieves or surpasses state-of-the-art results, given only a fraction of its competitors' runtime resources. Apart from image formation itself, this talk will also discuss recent applications in interactive editing and differentiable rendering methods for radiance fields (NeRFshop, 3D Gaussian Splatting).

2023

PIXEL Seminar

14 December, 10:30 B013
Charline Grenier University of Strasbourg
Color-mapped noise vector fields for generating procedural micro-patterns
Stochastic micro-patterns successfully enhance the realism of virtual scenes. Procedural models using noise combined with transfer functions are extremely efficient to generate them. However, most patterns employ 1D transfer functions, which assign color, transparency, or other material attributes, based on a single scalar noise. Multi-dimensional transfer functions have received widespread attention in other fields, such as scientific volume rendering. However, their potential has not yet been well explored for modelling micro-patterns in the field of procedural texturing. We propose a procedural model for stochastic patterns, defined as the composition of a bi-dimensional transfer function (a.k.a. color-map) with a stochastic vector field. Our model encompasses several existing procedural noises, such as Gaussian noise and Phasor noise, and generates a much larger gamut of patterns, including locally structured patterns. It can also be used to procedurally enhance virtual terrains in real-time, for example by adding spatially varying erosion patterns. By adapting the Phasor noise to the specific characteristics of terrains (water flowing, control on slopes) we create relief details corresponding to the underlying terrain characteristics, that preserve the coherence of generated landforms and allow artistic control through a palette of control maps.

GAMBLE Seminar

26 octobre, 14:00 A008
Lionel Pournin Université Sorbonne Paris Nord
Kissing polytopes
Consider two disjoint lattice polytopes contained in the hypercube [0,k]^d. The question of how close such a pair of polytopes can be stems from various contexts where this minimal distance appears in complexity bounds of optimization algorithms. Nearly matching lower and upper bounds on this distance will be provided and its exact computation discussed. Similar bounds will be given in the case of disjoint rational polytopes whose binary encoding length is prescribed. This talk is based on joint work with Antoine Deza, Shmuel Onn, and Sebastian Pokutta.
Jean Cardinal Université Libre de Bruxelles
Improved Algebraic Degeneracy Testing
In the classical linear degeneracy testing problem, we are given n real numbers and a k-variate linear polynomial F, for some constant k, and have to determine whether there exist k numbers a1, .. ,ak from the set such that F(a1, .. ,ak)=0. We consider a generalization of this problem in which F is an arbitrary constant-degree polynomial, we are given k sets of n numbers, and have to determine whether there exists a k-tuple of numbers, one in each set, on which F vanishes. We give the first improvements over the naive O*(n^{k-1}) algorithm for this problem (where the O*(.) notation omits subpolynomial factors), in both the real RAM and algebraic decision tree models of computation.
All our results rely on an algebraic generalization of the standard meet-in-the-middle algorithm for k-SUM, powered by recent algorithmic advances in the polynomial method for semi-algebraic range searching. In fact, our main technical result is much more broadly applicable, as it provides a general tool for detecting incidences and other interactions between points and algebraic surfaces in any dimension. In particular, it yields an efficient algorithm for a general, algebraic version of Hopcroft's point-line incidence detection problem in any dimension.
This is a joint work with Micha Sharir (S oC G'23).

PIXEL Seminar

5 octobre, 10:00 B013
Jing Ren ETH Zurich
Digital 3D Smocking Design
We develop an optimization-based method to model smocking, a surface embroidery technique that provides decorative geometric texturing while maintaining stretch properties of the fabric. During smocking, multiple pairs of points on the fabric are stitched together, creating non-manifold geometric features and visually pleasing textures. Designing smocking patterns is challenging, because the outcome of stitching is unpredictable: the final texture is often revealed only when the whole smocking process is completed, necessitating painstaking physical fabrication and time consuming trial-and-error experimentation. This motivates us to seek a digital smocking design method. Straightforward attempts to compute smocked fabric geometry using surface deformation or cloth simulation methods fail to produce realistic results, likely due to the intricate structure of the designs, the large number of contacts and high-curvature folds. We instead formulate smocking as a graph embedding and shape deformation problem. We extract a coarse graph representing the fabric and the stitching constraints, and then derive the graph structure of the smocked result. We solve for the 3D embedding of this graph, which in turn reliably guides the deformation of the high-resolution fabric mesh. Our optimization based method is simple, efficient, and flexible, which allows us to build an interactive system for smocking pattern exploration. To demonstrate the accuracy of our method, we compare our results to real fabrications on a large set of smocking patterns.

Day of the Department / Journée des doctorants du département

4 juillet 2023, salle C005

Camille Lanuel. Gamble. A toolbox for hyperbolic surfaces
Hyperbolic surfaces are 2-dimensional Riemannian manifolds that are locally isometric to the hyperbolic plane. They are hard to study in practice and the litterature lacks of tools to handle them. The diameter of a surface is a natural parameter to consider. However, computing it for a generic hyperbolic surface is hopeless, so my goal is to find an algorithm to approximate it.

Bastien Laboureix. Adagio. Connexité des hyperplans arithmétiques
Quand vous étiez petits, on vous a dit que les droites étaient continues et n'avaient pas d'épaisseur. Mais, en prenant une image numérique de droite et en zoomant au maximum, on observe plutôt un amas de pixel qu'une forme rectiligne continue. Et si nous étudiions ces droites numériques, discrètes, plutôt que leurs homologues euclidiennes ? Et si nous nous intéressions à une nouvelle géométrie ? Car, au-delà des droites, on peut regarder des segments, des polygones, voire monter en dimension et étudier des plans, des sphères, des hyperplans. Evidemment, la géométrie euclidienne ne s'applique pas sur les pixels : plus de division, adieu les limites, tout n'est plus qu'arithmétique ! Recommençons donc la géométrie depuis le début, via un problème simple sur les plans !

Haetham Al Aswad. Caramba. Discrete Logarithm Factory
The Number Field Sieve (NFS) and its numerous variants is the best algorithm to compute discrete logarithms in finite fields of medium and large characteristic. We present an algorithm to quickly compute discrete logarithms in a wide range of finite fields at the cost of a unique precomputation. The original idea was the Factorization Factory introduced by Coppersmith to deal with the integer factorization problem. In 2013, Barbulescu adapted the Factory idea to the discrete logarithm in prime finite fields (i.e. with extension degree equal to one). Our work generalizes the Factory idea to the discrete logarithm in finite fields of any extension degree. We combine this idea with two other variants of NFS, namely the tower and special variant. This combination leads to improvements in the asymptotic complexity. Besides, we lay out analytic estimates of the practicality of this method for 1024-bit targets and extension degree 6.

Yoann Coudert-Osmont. Pixel. A new quantization algorithm for quad remeshing
In the context of numerical simulation using finite element method, quadrilaterals meshes are sometimes preferred to triangular meshes. While generating triangular meshes is well handled, generating quad meshes is more difficult. Some methods are robust and some others produce high-quality meshes but may fail. We are interested in the global parametrization method which belongs to the second category. First, I will explain how this method works. Secondly I will present a new algorithm we have designed to solve one of the last steps of this method, which involve an integer-valued optimization problem.

Marco Freire. MFX. PCBend: Light Up Your 3D Shapes With Foldable Circuit Boards
Have you ever wanted to make a screen out of an object? Now you can with PCBend, a pipeline for automatic foldable circuit layout generation. We unfold an input object and use it as the blueprint for a printed circuit board, which we densely pack with addressable RGB LEDs. The pipeline outputs fabrication-ready files, all that remains is passing the order, 3D printing a core, and putting everything together. You can design custom lighting effects with a shader-like interface and make stunning visuals!

Ana Margarita Rodriguez Cordero. Caramba. T-wise independence for block ciphers
At CRYPTO 2021, Liu, Tessaro and Vaikuntanathan used the notion of (almost) t-wise independence to prove the security of block ciphers. This notion studies how close t distinct outputs of the cipher are to t uniform sampled input elements. In particular, they applied this idea to the AES cipher and used pairwise independence to assess its security against linear and differential attacks. In this talk I'll explain this technique and give leads to extend its use.

Antoine Leudière. Caramba. Drinfeld modules in SageMath
Drinfeld modules are mathematical objects that were introduced in the 1970s to answer profound questions in algebra, particularly in the context of the class field theory for function fields. Over time, the theory of Drinfeld modules has become well-established and is now recognized as an essential tool in various significant areas of Mathematics, such as the Langlands program. Notably, Laurent Lafforgue, who used Drinfeld modules to solve open problems from the Langlands program for function fields, was awarded with the Fields Medal in 2002.
Prior to our contribution, Drinfeld modules were absent from all standard distributions of computer algebra systems. We decided to implement Drinfeld modules in SageMath - a popular free and open source computer algebra system. Our implementation is available in the standard distribution of SageMath since version 10.0.
In this presentation, we will review of the development process, with a focus on the crucial issue of data representation. We will see that Drinfeld modules do not directly fit the SageMath paradigm of object representation. Our primary task was thus to to find the best compromise between ecosystem integration, mathematical satisfaction, and interface elegance.

Radhouane Jilani. Tangram. Simulation of catheter dynamics for neuroradiology
The mechanical thrombectomy procedure is used to treat ischemic strokes. This method employs a long, flexible catheter that navigates through the vascular system in order to extract blood clots. Building a computer-based simulator can help clinicians in preparing a patient treatment. Simulation of this procedure involves solving the constrained dynamics of the catheter. By leveraging its slenderness, the Cosserat theory can be applied. It models the catheter as a one-dimensional oriented curve that evolves according to a system of coupled non-linear partial differential equations. This approach is faster than finite element methods, while maintaining high accuracy. Cosserat dynamics can be solved using staggered grid discretization, but the resulting equations may become stiff and the constrained motion may exhibit unrealistic vibratory behaviors. We adopted a continuous approach by treating the dynamic system as a boundary value problem, and solved it using an orthogonal collocation method. Our method was compared to both the shooting method and discrete element methods on validation tests from the literature. It shows that our approach provides a good compromise between accuracy and computational efficiency.

Aude Marêché. Adagio. Analyse locale d'une surface discrète par secteurs planaires et application à l'estimation de la normale
Les applications d'extraction de caractéristiques géométriques nécessitent une analyse de la surface des objets discrets. Un des aspects de cette analyse peut être l'étude locale de la planéité du voisinage d'un point sur une surface. Nous proposons dans ce contexte une approche par découpage d'un voisinage circulaire non planaire en secteurs angulaires planaires autour d'un point, au moyen d'algorithmes classiques de reconnaissance de morceaux de plans discrets. Elle nous permet, grâce à une analyse locale, de mettre en évidence des éléments de la structure de la surface. Afin de démontrer la pertinence de ces découpages, nous en dérivons un estimateur de la normale en chaque point d'une surface discrète, avec des résultats comparables à ceux de l'état de l'art.

MFX Seminar

22 juin, 13:30 A008
Silvia Sellán University of Toronto
Uncertain Surface Reconstruction
We propose a method to introduce uncertainty to the surface reconstruction problem. Specifically, we introduce a statistical extension of the classic Poisson Surface Reconstruction algorithm for recovering shapes from 3D point clouds. Instead of outputting an implicit function, we represent the reconstructed shape as a modified Gaussian Process, which allows us to conduct statistical queries (e.g., the likelihood of a point in space being on the surface or inside a solid). We show that this perspective improves PSR's integration into the online scanning process, broadens its application realm, and opens the door to other lines of research such as applying task-specific priors.

2022

Gamble Seminar

27 octobre, 14:30 A006
Jean Cardinal Université libre de Bruxelles
Inapproximability of shortest paths on perfect matching polytopes
We consider the computational problem of finding short paths in the skeleton of the perfect matching polytope of a bipartite graph. We prove that unless P=NP, there is no polynomial-time algorithm that computes a path of constant length between two vertices at distance two of the perfect matching polytope of a bipartite graph. This answers negatively a question posed by Ito, Kakimura, Kamiyama, Kobayashi and Okamoto [SIAM Journal on Discrete Mathematics, 36(2), pp. 1102-1123 (2022)]. Assuming the Exponential Time Hypothesis we prove the stronger result that there exists no polynomial-time algorithm computing a path of length at most (1/2-o(1)) log n / (log log n) between two vertices at distance 2 of the perfect matching polytope of an n-vertex bipartite graph. These results remain true if the bipartite graph is restricted to be of maximum degree 3. The above has the following interesting implication for the performance of pivot rules for the simplex algorithm on simply-structured combinatorial polytopes: If P≠NP, then for every simplex pivot rule executable in polynomial time and every constant k there exists a linear program on a perfect matching polytope and a starting vertex of the polytope such that the optimal solution can be reached in two monotone steps from the starting vertex, yet the pivot rule will require at least k steps to reach the optimal solution. This result remains true if in addition so-called circuit pivots are allowed.

Gamble Seminar

27 octobre, 15:20 A006
Lionel Pournin Université Sorbonne Paris-Nord
Distance, strong convexity, flagness, and associahedra
One can always transform a triangulation of a convex polygon into another by performing a sequence of edge flips, which amounts to follow a path in the graph G of the associahedron. The least number of flips required to do so is then a distance in that graph whose estimation is instrumental in a variety of contexts, as for instance in computational biology, in computer science, or in algebraic topology. On the other hand, it is known that paths in G correspond to a certain kind of 3-dimensional triangulation. This talk is about the recent proof that these 3-dimensional triangulations are flag when the corresponding path is a geodesic. This result, that provides a new powerful tool to study the geometry of G, can be thought of as a 3-dimensional analogue of a well-known strong convexity property of G. Several consequences on the computation of distances in G and on strong convexity in related graphs will be discussed. This talk is based on joint work with Zili Wang (Dartmouth College).

Tangram Seminar

10 octobre, 10:00 C103
Douglas Perrin Harvard Biorobotics Lab
Desktop to bedside: Bespoke application development to translate computer science to clinical tools
In this talk, I will review the process of moving computer science to clinical applications, what I call Desktop-to-Bedside (a play on Bench-to-Bedside), and the challenges faced by conducting software development inside a hospital vs. a more traditional technical environment. I will sketch out a pipeline for Desktop-to-Beside and give a high-level description of several projects, how far they have made it through this pipeline, and their pain points.

Tangram Seminar

10 octobre, 10:00 C103
Peter E. Hammer Harvard Biorobotics Lab
Quantitative approaches for preoperative planning in aortic valve repair in childrenâ€
Surgical repair of heart valves remains among the most challenging procedures in cardiovascular surgery.Patient-specific computer simulation has been developed as a potential tool to enable surgeons to test proposed valve repair strategies prior to surgery in order to achieve more reliable repairs and better outcomes. Many groups worldwide have been making steady progress developing these image-based computational technologies over decades. Despite this progress, these technologies have not yet matured to the point of clinical utility, leaving surgeons to continue to rely on clinical experience and subjective methods in their day-to-day surgical practice. In this talk, I will present efforts that live in the middle ground between image-based computational surgical planning and the current approach of improvising in the OR based on clinical judgement. These emerging, quantitative methods rely on preoperative or intraoperative measurements of valve features and simple, conceptual models of valve relationships and function.

Gamble Seminar

20 septembre, 14:00 A008
André Nusser MPI
Fine-Grained Complexity and Algorithm Engineering in Computational Geometry
Computer science as a field aims to better understand the power and limitations of computation but also enables new results in fields that crucially rely on computation. While on first glance it seems that algorithm design should be the central area of research in this regard, progress also very much relies on complexity theory to understand the inherent hardness of certain problems, and an engineering approach, to transfer the theoretical knowledge into practical knowledge that can then be further exploited. In this spirit, we consider three central parts of algorithms research in this talk: algorithm design, (fine-grained) complexity lower bounds, and algorithm engineering. More concretely, we consider results in these areas for various geometric similarity measures like Fréchet distance, Hausdorff distance under translation, and dynamic time warping under translation.

Gamble Seminar

20 septembre, 15:00 A008
Justin Dallant ULB
Conditional lower bounds for dynamic geometric problems.
Fine-grained computational hardness conjecture and conditional lower bounds on complexity have been a familiar tool in the computational geometer's toolkit ever since the seminal work of Gajentaan and Overmars (1995) introducing 3-SUM hardness. In the data structure world, the study of such polynomial lower bounds for dynamic problems was arguably pioneered (and certainly popularized) by Patrascu in 2010, when he introduced the so-called Multiphase problem. He used this problem as a stepping stone to show that many dynamic problems which seemed hard to solve in subpolynomial time had a good reason to be, as the contrary would violate the 3-SUM conjecture. In this talk I will go over these results of Patrascu connecting the 3-SUM problem to seemingly unrelated dynamic problems. We will then bring it back to geometry by seeing how the Multiphase problem allows us to obtain polynomial lower bounds for a variety of dynamic geometric problems where previously only upper bounds where known. These latter results form the basis of a recent ESA-22 paper which is joint work with John Iacono.

Day of the Department / Journée des doctorants du département

11 juillet 2022, salle A008
Nariman Khaledian, Tangram. Capturing Contact in Mitral Valve Dynamic Closure with Fluid-Structure Interaction Simulation.
Realistic fluid-structure interaction (FSI) simulation of the mitral valve opens the way toward planning for surgical repair. In the literature, blood leakage is identified by measuring the flow rate, but detailed information about closure efficiency is missing. We present in this paper an FSI model that improves the detection of blood leakage by building a map of contact.
Methods - Our model is based on the immersed boundary method that captures a map of contact and perfect closure of the mitral valve, without the presence of orifice holes, which often appear with existing methods. We also identified important factors influencing convergence issues.
Results - The method is demonstrated in three typical clinical situations: mitral valve with leakage, bulging, and healthy. In addition to the classical ways of evaluating MV closure, such as stress distribution and flow rate, the contact map provides easy detection of leakage with identification of the sources of leakage and a quality assessment of the closure.
Conclusions - Our method significantly improves the quality of the simulation and allows the identification of regurgitation as well as a spatial evaluation of the quality of valve closure. Comparably fast simulation, ability to simulate large deformation, and capturing detailed contact are the main aspects of the study.
Ongoing work - Currently, we are focused on implementing more complex material characteristics in the model to simulate a more realistic behavior of the mitral valve motion. Implementation of real mitral valve geometry based on medical imaging is another ongoing work that we are currently focused on.

David Desobry, Pixel. Quadrilateral meshing for large deformations.
We present a fully automatic method to produce quadrilateral meshes that stay valid despite deformations during a numerical simulation. Our approach is based on the Quadcover algorithm, used in computer graphics to generate high quality quad meshes. Frame field based algorithm like Quadcover are currently not used for simulations of high deformation because the quadrilateral meshes generated have no reason to remain of sufficient quality when we deform their geometry. We explain in this talk how we can take into account deformations that we already computed to produce quad meshes adapted to these coming geometrical changes.

Ana Rodriguez Cordero, Caramba. Differential cryptanalysis in block ciphers
In symmetric cryptography, block ciphers are widely used to secure the exchange of messages between parties. Cryptanalysis is responsible for testing the security of these ciphers to ensure that communications are secure. During this talk we will see what block ciphers are and how to study their security against differential attacks.

Radhouane Jilani, Tangram. Simulation prédictive pour la neuroradiologie interventionnelle.
Les AVC ischémiques tuent chaque année plusieurs millions de personnes dans le monde. La thrombectomie manuelle, consistant à amarrer le caillot sanguin pour déboucher l'artère est l'un des traitements les plus sûrs et les plus efficaces actuels. Elle nécessite la navigation d'un cathéter dans l'arbre vasculaire du patient jusqu'à atteindre le caillot, ce qui est un geste difficile. L'objectif de ma thèse est le développement d'une simulation précise et interactive qui aide à la planification d'une telle opération. Ainsi, il est crucial de modéliser avec précision le cathéter, son environnement et leurs interactions. Le modèle de cathéter de cosserat sera utilisé car il offre le meilleur compromis entre temps de calcul et précision. Les vaisseaux seront modélisés implicitement et un nouvel algorithme de gestion des contacts sera développé. Après une introduction à ma thèse et à l'état de l'art, je présenterai trois simulations qui reproduisent une expérience réelle de déploiement de cathéter.

Tom Masini, ABC. Dimension de Natarajan à marge des PMC.
Nous nous intéressons à l'utilisation des dimensions combinatoires pour majorer la probabilité d'erreur des classifieurs multi-classes à marge. Dans ce contexte, la dimension combinatoire de référence est la gamma-dimension. Cependant, son utilisation pâ tit de l'absence d'un bon résultat structurel. Nous proposons de contourner cette difficulté en substituant à cette dimension la dimension de Natarajan à marge. Pour illustrer le potentiel de cette démarche, nous étudions le cas particulier des perceptrons multi-couches.

Bastien Laboureix, Adagio. Connexité des hyperplans arithmétiques.
Quand vous étiez petits, on vous a dit que les droites étaient continues et n'avaient pas d'épaisseur. Mais, en prenant une image numérique de droite et en zoomant au maximum, on observe plutô t un amas de pixel qu'une forme rectiligne continue. Et si nous étudiions ces droites numériques, discrètes, plutô t que leurs homologues euclidiennes ? Et si nous nous intéressions à une nouvelle géométrie ? Car, au-delà des droites, on peut regarder des segments, des polygones, voire monter en dimension et étudier des plans, des sphères, des hyperplans. Evidemment, la géométrie euclidienne ne s'applique pas sur les pixels : plus de division, adieu les limites, tout n'est plus qu'arithmétique ! Recommençons donc la géométrie depuis le début, via un problème simple sur les plans !

Yoann Coudert-Osmont, Pixel. Closed space-filling curves with controlled orientation for 3D printing.
We explore the optimization of closed space-filling curves under orientation objectives. By solidifying material along the closed curve, solid layers of 3D prints can be manufactured in a single continuous extrusion motion. The control over orientation enables the deposition to align with specific directions in different areas, or to produce a locally uniform distribution of orientations, patterning the solidified volume in a precisely controlled manner. Our optimization framework proceeds in two steps. First, we cast a combinatorial problem, optimizing Hamiltonian cycles within a specially constructed graph. We rely on a stochastic optimization process based on local operators that modify a cycle while preserving its Hamiltonian property. Second, we use the result to initialize a geometric optimizer that improves the smoothness and uniform coverage of the cycle while further optimizing for alignment and orientation objectives.

Youssef Assis, Tangram. Aneurysm detection using deep learning.
The detection of intracranial aneurysms from Magnetic Resonance Angiography (MRA) 3D images is a rapidly growing problem of clinical importance, which is not only time-consuming for radiologists but also extremely difficult to automate. To overcome data scarcity and class imbalance problems related to aneurysm data, state-of-the-art methods are model-centric approaches, which are focused on network architecture and loss functions, but only achieve fair sensitivity with a high false positives rate. Our work mainly follows a data-centric approach, where we exploit the maximum of our weak annotations, a small-patch approach was combined with an adapted data sampling strategy, taking into account the specificities of aneurysms. Moreover, we investigated the impact of various network architectures for aneurysm detection, and compared them using performance metrics that are more relevant to object detection.

Leo Valque, Gamble. Rounding polygonal meshes
To build a 3D mesh, Boolean operations are often used. But the resulting points have rational coordinates and each term of the rational requires greater precision, so you will probably need to round the coordinates of those points. However, rounding can create intersections and corrupt your mesh. I will present our new algorithm to solve this problem in 3D and the first results of its implementation.

Gamble Seminar

8 juillet, 13:30 A006
Boris Bukh Carnegie Mellon University
Enumeration of interval graphs and d-representable complexes
How many essentially distinct ways are there to arrange n convex sets in Rd? Here, `essentially distinct' means `with different intersection pattern'. We discuss this question both in the dimension 1, where it amounts to counting the interval graphs, and in higher dimenions. Based on the joint works with Amzi Jeffs.

Gamble Seminar

30 juin, 14:30 A008
Krishna Menon Chennai Mathematical Institute
A branch statistic for trees
A hyperplane arrangement is a finite collection of affine hyperplanes in Euclidean space. Its regions are the connected components of the complement of these hyperplanes. By a theorem of Zaslavsky, the number of regions of a hyperplane arrangement is the sum of coefficients of its characteristic polynomial. In this talk, we study an important class of arrangements called extended Catalan arrangements. The regions of such arrangements are known to correspond to certain labeled trees. We define a statistic on these trees such that its distribution is given by the coefficients of the characteristic polynomial. We will end by looking at some other arrangements and interpretations of their characteristic polynomial coefficients. This talk is based on joint work with Priyavrat Deshpande. Preprint

SÉMINAIRE DU DÉPARTEMENT proposé par PIXEL

15 avril 10:00 C005
Yuri Nesterenko Siemens
A concept of a generalized Ginzburg-Landau theory for 3D frame fields design
Spherical harmonics-based formulation of the frame fields design problem has been recently introduced for hexadedral meshing. One of the main difficulties in applying this approach is the need to take into account restrictions corresponding to the hexahedral symmetries. We propose a solution to this problem introducing SO(3)-invariant energy function based on the implicit representation of the manifold of symmetric harmonics and closely related to the well-known Ginzburg-Landau functional. Further, we discuss a concept of a generalized Ginzburg-Landau theory and its possible practical outcome.

COLLOQUIUM DU LORIA, proposé par GAMBLE

7 avril 2022, 13:30, Amphi Gilles Kahn
Hugo Parlier, Université du Luxembourg
Playing puzzles on surfaces
la page du colloquium

SÉMINAIRE DU DÉPARTEMENT proposé par MFX

18 mars 10:30 C005
Géraldine Morin, Université de Toulouse
Des squelettes aux modèles (2D, 3D, reconstruits ou volumique)... et inversement !
Les représentations par squelette offrent une modélisation d'une forme 2D ou 3D de dimension inférieure : un ensemble de courbes pour les formes 2D, un ensemble de feuillets et de courbes pour les modèles 3D. Nous proposons tout d'abord un algorithme de d'estimation de squelette 2D efficace et robuste, qui permet de générer un squelette non bruité qui garantit une epsilon-approximation de la forme originale au sens de la distance de Hausdorff. Nous présentons brièvement les travaux en cours pour généraliser cette approche en 3D. Ensuite, nous verrons comment l'estimation robuste du squelette 2D peut permettre de proposer la reconstruction d'un objet tubulaire composé de branches. Enfin (least but not last), nous proposons un méthode de génération de modèles volumiques paramétriques continus à partir de squelettes curvilignes 3D. La cohérence de la topologie de l'objet volumique est assurée par l'utilisation des ensembles semi-simploïdaux. Les branches sont jointes aux sommets du squelette de façon continue et toute configuration topologique peut être générée.

SÉMINAIRE DU DÉPARTEMENT proposé par PIXEL

24 février 10:00 A008
Nicolas Donati, École polytechnique
Injecting Orientation into Spectral Shape Matching
Given two 3D surfaces, we propose to use intrinsic quantities to compute orientation aware near-isometries between these shapes. Previous techniques focused on matching the functional spaces of the two shapes to retrieve mappings between source and target shape. We shift focus to the vector field spaces of the shapes, also called tangent bundles. By considering the differentiate of the mapping, and imposing desirable properties on this object we are able to restrict the search space and only retrieve orientation-preserving conformal (angle preserving) maps between surfaces. The key idea to this approach is to represent tangent vector fields as complex field, and notice that if the mapping is conformal, its differentiate becomes a complex-linear map between the tangent bundles. This idea can be used to upgrade many spectral shape matching algorithms, as well as to transfer vector fields between curved domains simply and accurately.

2021

SÉMINAIRE DU DÉPARTEMENT proposé par Caramba.

16 décembre 2021, 10h30 A008
Guillaume Moroz, Gamble
New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems
We present a new data structure to approximate accurately and efficiently a polynomial f of degree d given as a list of coefficients. Its properties allow us to improve the state-of-the-art bounds on the bit complexity for the problems of root isolation and approximate multipoint evaluation. This data structure also leads to a new geometric criterion to detect ill-conditioned polynomials, implying notably that the standard condition number of the zeros of a polynomial is at least exponential in the number of roots of modulus less than 1/2 or greater than 2.

Gamble Seminar

22 juin, 14:30 Terrasse
Thomas Fernique, LIPN
Empilements de sphères de densité maximale
Il est bien connu que pour couvrir la plus grande proportion du plan Euclidien par des disques identiques disjoints, la meilleure façon est de centrer ces disques sur un réseau triangulaire. Ce problème peut être généralisé dans deux directions : en dimensions supérieures ou avec différentes tailles de disques. La première voie a été la plus étudiée (par exemple en dimension 3 avec la preuve de la conjecture de Kepler par Hales et Ferguson en 1998). Ici, on s'intéressera plutôt à la deuxième voie, en particulier le cas de deux tailles de disques.

MFX Seminar

June 14th, 4pm visio
Silvia Sellán University of Toronto
A deep dive into Swept Volumes
Abstract: Given a solid 3D shape and a trajectory of it over time, we compute its swept volume – the union of all points contained within the shape at some moment in time. We consider the representation of the input and output as implicit functions, and lift the problem to 4D spacetime, where we show the problem gains a continuous structure which avoids expensive global searches. We exploit this structure via a continuation method which marches and reconstructs the zero level set of the swept volume, using the temporal dimension to avoid erroneous solutions. We show that, compared to other methods, our approach is not restricted to a limited class of shapes or trajectories, is extremely robust, and its asymptotic complexity is an order lower than standards used in the industry, enabling its use in applications such as modeling, constructive solid geometry, and path planning.
Bio: Silvia Sellán is a second-year PhD student at the University of Toronto, supervised by professor Alec Jacobson. She has interned twice at Adobe Research and twice at the Fields Institute of Mathematical Sciences, and has published three first-author papers at ACM SIGGRAPH. Her research focuses on specific geometry processing challenges one encounters in data captured from the real world, and geometric data aimed at fabrication.

Tangram Seminar

28 mai visio
Gilles Simon Tangram, Loria
Jan van Eyck's perspectival system elucidated through computer vision

Days of the Department / Journées des doctorants du département

18 mai -- 17 juin 2021
18-21 mai : https://cnrs.zoom.us/j/97699373100     Meeting ID: 976 9937 3100     Passcode: jAD1vL
14-17 juin : https://cnrs.zoom.us/j/98368582262     Meeting ID: 983 6858 2262     Passcode: 2WvVBD