L'efficacité d'un algorithme est souvent obtenue par l'utilisation de structures de données élaborées qui entrainent une augmentation de la complexité algébrique de l'algorithme. Concevoir des algorithmes optimaux du point de vue de leur complexité en temps et de leur complexité algébrique est une direction de recherche nouvelle et prometteuse qui doit conduire à des algorithmes plus fiables et à une meilleure compréhension des algorithmes eux-mêmes.
Le stage fait suite à des travaux récents sur la complexité algébrique d'algorithmes du calcul des intersections d'un ensemble de segments . Ce travail peut être étendu au cas d'arcs de courbe et à la dimension trois, et à d'autres problèmes. Le stage pourra aborder une ou plusieurs de ces extensions. Il comportera une partie théorique et un travail de programmation en C++ qui s'appuiera sur la bibliothèque d'algorithmes géométriques CGAL.
Le stage s'inscrit dans le cadre d'un projet européen mené en collaboration avec six autres équipes. Il pourra se prolonger en thèse.