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.


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

Tangram Seminar

10 octobre, 10:00 C103
Peter E. Hammer Harvard Biorobotics Lab
Quantitative approaches for preoperative planning in aortic valve repair in children”

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


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.


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


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.


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.



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 :     Meeting ID: 976 9937 3100     Passcode: jAD1vL
14-17 juin :     Meeting ID: 983 6858 2262     Passcode: 2WvVBD