Distance de Manhattan

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La distance de Manhattan, appelée aussi taxi-distance, est la distance entre deux points parcourue par un taxi lorsqu'il se déplace dans une ville américaine où les rues sont agencées selon un réseau ou quadrillage. Un taxi-chemin est le trajet fait par un taxi lorsqu'il se déplace d'un nœud de réseau à un autre en utilisant les déplacements horizontaux et verticaux du réseau.

Définition[modifier | modifier le code]

Entre deux points A et B, de coordonnées respectives (X_A,Y_A) et (X_B,Y_B), la distance de Manhattan est définie par :

d(A,B)=|X_B-X_A|+|Y_B-Y_A|

Autrement dit : c'est la distance associée à la norme 1.

Propriétés[modifier | modifier le code]

Distance de Manhattan (chemins rouge, jaune et bleu) contre distance euclidienne en vert.

On montre que si on oriente le réseau et que l'on définit des déplacements élémentaires positifs et négatifs, la distance de Manhattan est indépendante du chemin parcouru à l'intérieur d'un réseau fini. Ainsi, sur l'image de droite, les chemins rouge, bleu et jaune ont la même distance (ici égale à 12).

Lien externe[modifier | modifier le code]