Geometria del taxista

Distància de Manhattan contra distància Euclidiana: Les línies vermella, blava i groga tenen la mateixa longitud (12) en les geometries Euclidiana i del taxista. En la geometria euclidiana, la línia verda té una longitud igual a${\textstyle 6{\sqrt {2}}\approx 8.48}$, i és l'únic camí més curt.

La geometria del taxista, també coneguda com a mètrica del taxista o distància de Manhattan, és una forma de geometria on es reemplacen aspectes propis de la geometria euclidiana. Així per anar d'un punt a un altre només es pot seguir la direcció vertical o horitzontal, en la qual la funció de distància entre dos punts és la suma de les diferències absolutes de la seva coordenades cartesianes.

Aquest concepte va ser considerat per l'alemany Hermann Minkowski al segle xix. Es coneix també com distància rectilínia, distància L₁ o norma $\ell _{1}$ (veure espai L^p), o l'esmentada distància de Manhattan, amb les corresponents variacions del nom de la geometria. Aquesta darrera denominació fa referència a la quadrícula de la majoria dels carrers de l'illa de Manhattan (o de l'eixample de Barcelona), i que fa que el camí més curt que un taxi ha de recórrer entre dos punts de la ciutat no sigui la distància euclidiana.

Descripció

La distància de Manhattan $d_{1}$ entre dos vectors $\mathbf {p} ,\mathbf {q}$ en un espai vectorial real n-dimensional i amb un sistema de coordenades cartesianes fix és la suma de les longituds de les projeccions del segment de línia entre els punts sobre el sistema d'eixos coordinats. Més formalment,

$d_{1}(\mathbf {p} ,\mathbf {q} )=\|\mathbf {p} -\mathbf {q} \|_{1}=\sum _{i=1}^{n}|p_{i}-q_{i}|$

on $\mathbf {p} =(p_{1},p_{2},\dots ,p_{n})\,$ i $\mathbf {q} =(q_{1},q_{2},\dots ,q_{n})\,$ són vectors.

Per exemple, en el pla, la distància de Manhattan entre $(p_{1},p_{2})$ i $(q_{1},q_{2})$ és: $|p_{1}-q_{1}|+|p_{2}-q_{2}|$

La distància de Manhattan depèn de la rotació del sistema de coordenades, però no depèn de la seva reflexió sobre un eix coordinat o la seva translació. La geometria del taxista satisfà tots els axiomes de Hilbert, ja que es poden generar dos triangles amb dos costats cadascú i l'angle entre ells iguals i que no siguin congruents.

Propietats

Mediatriu

Tots aquells punts que estiguin a la mateixa distància entre els punts A i B defineixen una recta que coneixem com a mediatriu. Hem de construir un rectangle que estigui definit per A i B, amb longitud de a i b (dos dels costats diferents del rectangle). Es pot observar que la distància entre A i B és a+b.

Per construir la mediatriu entre dos punts, hem de buscar el lloc geomètric dels punts que estan a la mateixa distància d'un punt que de l'altre. Per tant, s'ha de dividir la distància entre els dos punts entre dos. [(a+b)/2] Anomenarem aquest segment lineal PQ.

Tots aquells punts que estan en el segment PQ, disten de la mateixa distància entre els punts A i B, igual que si fem una semirecta vertical a partir del punt P i del Q, els punts d'aquestes semirectes també estaran a la mateixa distància segons els punts A i B. Aquesta línia divideix el pla en dues regions de Voronoi.

Cercles en la geometria del taxista

Cercles en la geometria del taxista discreta i continua

Un cercle és un conjunt de punts amb una distància fixa a un punt denominat centre i que hom anomena radi. En la geometria del taxista la distància és determinada per una mètrica diferent a la de la geometria euclidiana, i la forma dels cercles també és diferent. En la geometria del taxista els cercles són quadrats amb els costats orientats en un angle de 45° amb els eixos coordinats. La imatge a l'esquerra mostra per què és així, indicant en vermell el conjunt de tots els punts amb una distància fixe a un centre indicat en blau.

Quan la mida dels blocs de la ciutat disminueix, els punts es tornen més nombrosos i esdevenen un quadrat girat en una geometria del taxista continua. Mentre que cada costat tindria una longitud √2r emprant una mètrica euclidiana, on r és el radi del cercle, la seva longitud en la geometria del taxista és 2r. Així doncs la longitud de la circumferència és 8r.

La fórmula per a un cercle unitari en la geometria del taxista és $|x|+|y|=1$ en coordenades cartesianes i $r={\frac {1}{|\sin \theta |+|\cos \theta |}}$  en coordenades polars.

En un pla, un cercle de radi r segons la distància de Chebyshev (L_∞) també és un quadrat amb costats de longitud 2r i paral·lels als eixos de coordenades. Així la distància planar de Chebyshev es pot considerar equivalent, per rotació i escalat, a la distància planar del taxista. Ara bé, aquesta equivalència entre les mètriques L₁ y L_∞ no es compleix en dimensions majors.

L'ús de la distància de Manhattan introdueix un concepte estrany: quan la resolució de la geometria del taxista és molt gran, apropant-se a l'infinit (la mida de la divisió dels eixos s'aproxima a zero), sembla intuïtiu que la distància de Manhattan s'aproparia a la mètrica euclidiana (${\sqrt {{|x_{1}-x_{2}|}^{2}+{|y_{1}-y_{2}|}^{2}}}$) però no és així. Això és, essencialment, una conseqüència del fet d'estar forçat a moure’s sobre un únic eix. Quan es segueix la mètrica de Manhattan, un no es pot moure diagonalment (en més d'un eix simultàniament).

Història

Al segle xix, els matemàtics i els físics estaven començant a explorar formes de crear geometries no euclidianes. Normalment, s'atribueix a Hermann Minkowski la introducció de la geometria del taxista, juntament amb tota una família de geometries diferents, basades en diferents maneres de mesurar la distància entre punts.

Aplicacions

La geometria del taxista pot ser utilitzada d'una manera diferent per mesurar distàncies, en totes aquelles situacions on la distància Euclidea no pot ser aplicada.

Mesura de distàncies als escacs

Una de les aplicacions més bàsiques que es poden trobar amb la distància de Manhattan són els escacs. Les peces de la torre es mouen només horitzontalment o verticalment. Els cavalls es mouen en forma de L, un total de quatre unitats. Tot i que pertanyen a la distància de taxis, no proporciona una aplicació adequada de la geometria. Els alfils utilitzen la distància de Manhattan (entre els quadrats del mateix color) en el quadre rotat en 45 graus, és a dir, amb les seves diagonals com a eixos coordinats. Reis i reines usen la distància de Txebixov.

Vegeu també

• Espai mètric
• Espai vectorial normat
• Distància de Hamming

Enllaços externs

• Black, Paul E. Manhattan distance a Dictionary of Algorithms and Data Structures. NIST
• Malkevitch J. Taxi! American Mathematical Society