Actualité - Annonce de Thèse

Date : 27 mai 2021 10:30 - CROMBEZ Loïc - Visio-conférence

Finding Digital Convexity

Le sujet porte sur l'étude de problèmes algorithmiques posés dans le cadre de la géométrie digitale, autrement dit la géométrie des parties de Z^d, là où la géométrie classique se définit comme la géométrie des parties de R^d. Nous nous intéressons à la convexité digitale. Le premier problème étudié consiste à reconnaître les convexes digitaux en dimension 2, problème pour lequel un algorithme linéaire est proposé. Le second problème consiste à trouver un polygone convexe avec un nombre minimal de sommets contenant une partie donnée, problème lui aussi résolu en temps linéaire. Le troisième problème habituellement appelé "potato peeling" consiste à trouver le plus grand convexe inclus dans une partie donnée. Nous le résolvons dans le cas digital avec un algorithme en O(n^3). On étudie enfin une généralisation du problème en la recherche de la plus grande union de k convexes digitaux incluses dans une partie donnée, problème résolu avec une complexité O(n^(4k+1)).
La dernière partie de la présentation portera sur des travaux hors manuscrit réalisés pendant les trois années de thèse mais moins directement connectés à la thématique centrale étudiée.

 

Jury :
Sándor Fekete, Professeur des Universités, Technische Universität Braunschweig (rapporteur)
Rodrigo Silveira, Maître de conférences, Universitat Politècnica de Catalunya (rapporteur)
David Coeurjolly, DR CNRS, LIRIS, Université Claude Bernard Lyon 1 (rapporteur)
Olivier Devillers, DR CNRS, LORIA, Université de Lorraine (examinateur)
Isabelle Sivignon, CR CNRS, Gipsa-Lab, Université de Grenoble (examinatrice)
Fabien Feschet, Professeur des Université, LIMOS, Université Clermont Auvergne (examinateur)
Guilherme Dias Da Fonseca, Maître de conférences, LIS, Université Aix-Marseille (co-directeur)
Yan Gerard, Maître de conférences, LIMOS, Université Clermont Auvergne (co-directeur).