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.

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

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 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.

Lien externe[modifier | modifier le code]