Le prochain colloquium du Loria aura lieu le mardi 10 décembre 2024 à 13 h 30 dans l’amphithéâtre.
Nous aurons le plaisir d’accueillir Jean Cardinal, professeur à l’Université Libre de Bruxelles, avec une présentation (en anglais) intitulée “Combinatorics, Geometry, and Algorithms“.
Abstract:
Numerous interactions exist between the fields of combinatorics, discrete geometry — in the tradition initiated, among others, by Paul Erdős — and theoretical computer science. It is often fruitful to consider combinatorial abstractions to tackle computational geometry problems, and conversely, geometry crops up sometimes unexpectedly in a purely discrete computational context.
We will illustrate these interactions through an example related to our research.
In computational geometry, it can be useful to encode sets of points in the plane by storing the orientation (clockwise or counterclockwise) of every triple of points. By considering the properties that these orientations must satisfy as axioms, one can relate these encodings to tools from matroid theory. These ideas have helped to identify a specific complexity class that revealed useful for better understanding the difficulty of a number of problems in computational geometry.
We will strive to minimize technical content and make the presentation accessible to everyone.
Biography:
Jean Cardinal is a professor of computer science at the Université libre de Bruxelles (ULB), in Brussels, Belgium, and co-director of the Algorithms Research Group. His research is in the field of theoretical computer science and discrete mathematics, in particular computational geometry, the branch of computer science devoted to the design and analysis of algorithms for problems involving geometric data. Heobtained his PhD from ULB in 2001, with a fellowship from the FNRS, and has held visiting professorships at various institutions since then, the most recent ones being at ETH Zurich and Université Sorbonne Paris Nord.