Offre de thèse
Types d'ordre, décomposition et complexité
Date limite de candidature
03-05-2024
Date de début de contrat
01-10-2024
Directeur de thèse
GOAOC Xavier
Encadrement
Alfredo Hubard, Maitre de conférence, Université Gustave Eiffel
Type de contrat
école doctorale
équipe
GAMBLEcontexte
Le type d'ordre d'un ensemble fini de points du plan est une structure combinatoire qui encode la position relative des points les uns par rapport aux autres. Il peut par exemple s'encoder par la fonction (dite 'chirotope') qui à chaque triplet d'indices (i,j,k) associe +1 si le kème point est à gauche de la droite joignant le ième au jème, orientée du ième au jème, et -1 sinon. Le type d'ordre d'un ensemble de points détermine un grand nombre de ses propriétés, par exemple son enveloppe convexe ou encore les graphes qu'il est possible de dessiner rectilinéairement sur ces sommets sans croisement. L'objectif de cette thèse est de contribuer à l'étude du problème de l'exploration de l'ensemble des types d'ordre. Il s'agira par exemple de développer l'algorithmique des décompositions modulaires, d'explorer l'effet de l'interdiction d'un motif, ou encore d'examiner la possibilité de génération aléatoire efficace.spécialité
Informatiquelaboratoire
LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Mots clés
Géométrie algorithmique, Structures discrètes, Décompositions modulaires, motifs interdits
Détail de l'offre
Les types d'ordre sont des structures discrètes induites par des ensembles finis de points du plan ou de l'espace. L'objectif de cette thèse est de contribuer à l'étude des propriétés algorithmiques et de complexité des types d'ordre, et plus particulièrement aux méthodes permettant d'explorer l'ensemble de ces structures.
Keywords
Computational geometry, Discrete structures, Modular decompositions, forbidden patterns
Subject details
Order types are discrete structures induced by finite point sets in the plane or higher dimension. The objective of this thesis is to contribute to the study of their algorithmic and complexity properties, and more specifically to methods for exploring the set of order types.
Profil du candidat
- master en informatique ou mathématiques. Aisance en français ou en anglais.
- un intérêt pour l'articulation entre informatique et mathématiques
- des connaissances solides dans un domaine tel que la géométrie algorithmique et combinatoire, l'algorithmique, la théorie de la complexité, ... sont un plus
Candidate profile
- Msc in computer science or mathematics. Fluency in french or english.
- An interest for the interplay of computer science and mathematics.
- A solid background in an area such as discrete and computational geometry, algorithms, complexity theory... is a plus.
Référence biblio
[1] Jacob E Goodman and Richard Pollack. Allowable sequences and order types in discrete and com-
putational geometry. In New trends in discrete and computational geometry, pages 103–134. Springer,
1993.
[2] Peter Shor. Stretchability of pseudolines is NP-hard. Applied Geometry and Discrete Mathematics-The
Victor Klee Festschrift, 1991.
[3] Jürgen Richter-Gebert. Mnëv's universality theorem revisited. Sém. Lothar. Combin, 34:B34h, 1995.
[4] Convex hulls of random order types, Xavier Goaoc and Emo Welzl. Journal of the ACM, 70(1): 1--47, 2023.
[5] A canonical tree decomposition for order types, and some applications. Mathilde Bouvel, Valentin Féray, Xavier Goaoc, Florent Koechlin, arXiv:2403.10311.