Distance de Manhattan

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Distance de Manhattan (chemins rouge, jaune et bleu) contre distance euclidienne en vert.

La distance de Manhattan[1],[2], appelée aussi taxi-distance[3], est la distance entre deux points parcourue par un taxi lorsqu'il se déplace dans une ville où les rues sont agencées selon un réseau ou quadrillage. Un taxi-chemin[3] est le trajet fait par un taxi lorsqu'il se déplace d'un nœud du 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]

On montre que si l'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, la distance entre les deux points noirs, qu'on les joigne par les chemins rouge, bleu ou jaune, est identique (et égale à 12).

Références[modifier | modifier le code]