Sujet : Spanner planaire de degré 3 pour des points couverts par k lignes du plan

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 : algorithmique de graphe, graphe géométrique, spanner planaire

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.

La construction, pour tout ensemble de points, d'un graphe spanner planaire de maximum degré 3 et de facteur d'étirement borné est un problème ouvert majeur du domaine. L'objectif de ce stage est d'étudier ce problème lorsque l'ensemble des points à la propriété de pouvoir être couvert par $k$ lignes, et plus particulièrement 3 lignes parallèles. On pourra s'inspirer des solutions proposées par [BBDCx17] et [DG16b] dans le cas où les points peuvent être couverts par une grille rectangulaire.

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]

[BBDCx17] Ahmad Biniaz, Prosenjit Bose, Jean-Lou de Carufel, Cyril Gavoille, Anil Maheshwari, and Michiel Smid. Towards plane spanners of degree 3. Journal of Computational Geometry, 8(1), 2017.

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

[DG16b] Adrian Dumitrescu and Anirban Ghosh. Lattice spanners of low degree. In 2nd International Conference on Algorithms and Discrete Applied Mathematics (CALDAM), volume 9602 of Lecture Notes in Computer Science, pages 152-163. Springer-Verlag, February 2016.