Luca Castelli Aleardi

La localisation de points dans une subdivision planaire est l'un des problèmes centrales de la géométrie algorithmique. Comme il s'agit d'une étape cruciale dans des nombreux algorithmes géométriques et applications, ce problème a suscité l'interet des chercheurs du point de vue théorique ainsi que pratique. De nombreuse solutions existent, en particulier pour le cas des triangulations planaires, l'un des plus étudiés. Comme nous avons vu dans le cours INF562, il existe des solutions simples à mettre en place (marche par visibilité), mais dont la complexité n'est pas asymptotiquement optimale. Des solutions optimales (avec un temps de requete logarithmique, au pire cas) ont été proposées, mais leur implementation est parfois couteuse (à cause des structures de données plus sophistiquées qu'il faut manipuler).
Des travaux récents ont cherché de combiner les différents approches (ou leurs variantes) basées sur des marches dans une triangulation, ainsi que sur la hierarchie de Delaunay. Les résultats experimentaux sont intéressants, et montre que des solutions faciles à mettre en place permettent d'obtenir des méthodes de localisation efficace et adaptatives.