Avstand fra Manhattan

Den avstand av Manhattan , også kalt taxi -Avstand er avstanden mellom to punkter gjennom hvilke en taxi når den beveger seg i en by, hvor gatene er anordnet i en matrise eller et gitter . Denne avstanden ble definert av Hermann Minkowski . En drosjebane er reisen som en taxi tar når den beveger seg fra en nettverksnode til en annen ved hjelp av de horisontale og vertikale bevegelsene til nettverket.

Definisjon

Mellom to punkter A og B , med respektive koordinater og , er avstanden fra Manhattan definert av: $(X_ {A}, Y_ {A})$ $(X_ {B}, Y_ {B})$

{\ displaystyle d (A, B) = | X_ {B} -X_ {A} | + | Y_ {B} -Y_ {A} |}

Med andre ord er det avstanden som er knyttet til norm 1 .

Eiendommer

Vi viser at hvis vi orienterer nettverket og definerer positive og negative elementære forskyvninger, er avstanden på Manhattan uavhengig av banen som er reist i et begrenset nettverk. På bildet til høyre er avstanden mellom de to svarte punktene, enten de er forbundet med den røde, blå eller gule banen, identisk (og lik 12).

Referanser

(in) " Manhattan distance " på NIST .
“ Distance from Manhattan, ” fra Google Books .
“ Taxi-way and taxi-distance ” [PDF] , på ULB .