Distanza da Manhattan

La distanza di Manhattan , detta anche di taxi -distanza è la distanza tra due punti attraverso i quali un taxi quando si muove in una città dove le strade sono disposti in una matrice o griglia . Questa distanza è stata definita da Hermann Minkowski . Una pista-taxi è il viaggio compiuto da un taxi mentre si sposta da un nodo della rete all'altro utilizzando i movimenti orizzontali e verticali della rete.

Definizione

Tra due punti A e B , con rispettive coordinate e , la distanza da Manhattan è definita da: (XA,sìA){\ stile di visualizzazione (X_ {A}, Y_ {A})}(XB,sìB){\ stile di visualizzazione (X_ {B}, Y_ {B})}

d(A,B)=|XB-XA|+|sìB-sìA|{\ stile di visualizzazione d (A, B) = | X_ {B} -X_ {A} | + | Y_ {B} -Y_ {A} |}

In altre parole, è la distanza associata alla norma 1 .

Proprietà

Mostriamo che se orientiamo la rete e definiamo spostamenti elementari positivi e negativi, la distanza di Manhattan è indipendente dal cammino percorso all'interno di una rete finita. Quindi, nell'immagine a destra, la distanza tra i due punti neri, siano essi uniti dai percorsi rosso, blu o giallo, è identica (e uguale a 12).

Riferimenti

1. (in) "  Distanza di Manhattan  " su NIST .
2. "  Distanza da Manhattan  " , da Google Libri .
3. “  taxi-way e taxi a distanza  ” [PDF] , l'ULB .