Sujet : Triangulation optimale d'un n-gon régulier

Responsable : Cyril Gavoille
Contact : gavoille@labri.fr
Équipe : Combinatoire et Algorithmique
Thème : Algorithmique Distribuée
Type : stage Master Informatique
Durée : 4 mois (février - mai 2018)
Lieu : LaBRI
Financement : oui
Mot-clés : graphe géométrique, triangulation, plus court chemin

Présentation du sujet :

Un problème classique de géométrie algorithmique consiste à calculer un graphe couvrant un ensemble de points donné du plan. La triangulation de Delaunay est une façon de faire: deux points sont adjacents dans la triangulation de Delaunay si et seulement s'il existe un cercle passant pour les deux points et dont l'intérieur ne contient aucun autre point. De manière générale on parle de graphes géométriques, les sommets étant des points du plan (ou d'un espace géométrique), et les arêtes étant définies à partir des coordonnées des points extrémités et valuées par la distance entre ces mêmes extrémités.

On souhaite ainsi construire à partir d'un ensemble quelconque de $n$ points du plan d'un graphe géométrique $G$ (appelé aussi spanner), à l'instar de la triangulation de Delaunay, possédant plusieurs propriétés par lesquelles: le graphe $G$ est sans croisement d'arêtes (planaire), il est de degré maximum est borné, le facteur d'étirement est borné. Le facteur d'étirement est le plus petit réel $s$ tel que $\mathrm{dist}_G(p,q) \leqslant s\cdot \Vert p-q\Vert$ pour tout sommet $p,q$ de $G$. Dit autrement on souhaite, pour chaque paire de points, que la distance dans le graphe $G$ entre ces points (le coût d'un plus court chemin) ne soit pas trop éloignée (au plus d'un facteur $s$) de la distance euclidienne entre ces mêmes points. Voir [BS13a] pour une liste détaillés de problèmes ouverts du domaine.

L'objectif de ce stage est d'étudier les triangulations d'ensembles de $n$ points placés sur les sommets d'un $n$-gon réguliers. Il est connu que le facteur d'étirement de toute triangulation d'un $n$-gon est au moins 1.4308 [DG16], valeur atteinte pour $n=23$. Il s'agira de construire des classes de triangulations afin de déterminer un majorant sur le meilleur facteur d'étirement possibles des $n$-gon réguliers pour toute valeur de $n$. La question pourra être étendue au cas où le degré maximum de la triangulation recherchée est borné.

Ce sujet se rattache à un domaine de recherche novateur et peut faire l'objet, selon la motivation et le travail du candidat, d'une poursuite en thèse.

Références :

[login: gavoille, pwd: bib0]

[BS13a] Prosenjit Bose and Michiel Smid. On plane geometric spanners: A survey and open problems. Computational Geometry: Theory and Applications, 46:818-830, 2013.

[DG16] Adrian Dumitrescu and Anirban Ghosh. Lower bounds on the dilation of plane spanners. Technical Report 1509.07181v4 [cs.CG], arXiv, April 2016.