Distance de Manhattan

distance parcourue par un taxi

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, à l'image de Manhattan. Cette distance fut définie par Hermann Minkowski. 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.

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

Définition

modifier

Entre deux points A et B, de coordonnées respectives   et  , la distance de Manhattan est définie par :

 

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

Propriétés

modifier

La distance de Manhattan entre deux points du réseau est égale au nombre de déplacements élémentaires horizontaux ou verticaux permettant de joindre ces deux points, indépendamment du chemin choisi, pourvu que ces déplacements élémentaires se fassent toujours dans le même sens. 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).

Application

modifier

La distance de Manhattan est utilisée dans le domaine numérique pour sa capacité à donner des résultats relativement justes et rapides. En effet, elle ne travaille qu'avec des grandeurs entières qui permettent de minimiser le travail calculatoire exigé.

En biologie, elle permet de déterminer la proximité génétique ou selon des propriétés entre différentes espèces ou individus au sein d'une population, et de déterminer la probabilité d'appartenance d'un individu à un groupe en application avec l'algorithme des k plus proches voisins.

Références

modifier

Sur les autres projets Wikimedia :

  1. (en) Paul E. Black, « Manhattan distance », Dictionary of Algorithms and Data Structures, NIST.
  2. « Distance de Manhattan », sur Google Livres.
  3. a et b « Taxi-chemin et taxi-distance » [PDF], sur ULB.