Navigation dans le plan : résultats asymptotiques

Soit G =( V , E ) un graphe ; un algorithme de navigation/routage (sans mémoire) sur G est la donnée d’une application N de V x V dans V qui à ( s , t ) associe un point s ‘ (et qui vérifie N ( s , s ) = s ).

On peut interpréter les choses comme suit : s est le point de départ, t celui d’arrivée. Le noeud N ( s , t )= s ‘ nous donne la première étape du parcours d’un voyageur.

La condition N ( s , s ) = s signifie qu’une fois arrivé, s’il arrive, le voyageur s’arrête.

Si on pose, s 0 = s et pour i > 0, s i = N ( s ( i -1), t ), la suite des points s i donne la suite des étapes du voyageur.

Nous nous intéressons ici à des algorithmes de navigation dans le plan : les étapes possibles sont un ensemble de points S , et les algorithmes de navigation considérés sont construits en utilisant des critères géométriques (il s’agit de navigation à la boussole).

Nous montrons que si les points de S sont aléatoires, et si le nombre de points n de S tend vers l’infini, alors la distance parcourue par le voyageur converge lorsque n vers l’infini, vers une valeur que l’on détermine. D’autres résultats asymptotiques seront également proposés.

(travail commun avec Nicolas Bonichon, LaBRI).