Randomisation, sphères et déplacements de robots

Ce mémoire d'habilitation présente 14 articles différents, structurés en trois parties : algorithmes randomisés, algorithmes sur les sphères et placements de robots.Les algorithmes randomisés ont été un des sujets ``chauds'' de ces dernières années et nous proposons ici des travaux ayant trait à des algorithmes dynamiques ou semi-dynamiques : tout d'abord un schéma général d'algorithmes semi-dynamiques avec des applications aux diagrammes de Voronoï, aux diagrammes de Voronoï d'ordre k aux arrangements, et ensuite deux algorithmes dynamiques (permettant d'insérer et de supprimer des données) pour la triangulation de Delaunay et le calcul d'un arrangement de segments. D'autres résultats concernent des algorithmes statiques, notamment le calcul du squelette d'un polygone simple en temps O(n log* n).La deuxième partie explore différentes modélisations des sphères. On peut en déduire notamment un algorithme en O(tk log n) pour la triangulation de Delaunay de n points appartenant à k plans en 3 dimensions, si t désigne la taille du résultat; dans la cas de deux plans cet algorithme atteint une complexité optimale de O(t+n log n). Nous proposons également un algorithme de complexité O(n^ ceil(d/2) +n log n) pour le calcul de l'enveloppe convexe de n sphères en dimension d, et un algorithme optimal (quadratique) pour le calcul de la surface de Connolly.La dernière partie traite de problèmes spécifiques à la planification de trajectoires, un premier chapitre concerne le cas de plusieurs robots polygonaux en translation dans le plan: certaines configurations appellées double-contacts peuvent jouer un rôle particulier dans certains cas. Ensuite deux résultats à propos de robots à pattes : l'analyse d'un cas simple que nous avons baptisé robot araignée, et l'étude de la stabilité d'un robot un peu plus complexe