Calcolatore Distanza Manhattan (L1, Taxicab Geometry)

Calcolatore distanza Manhattan L1: 2D, 3D, N-dim, geometria taxicab, confronto con norme Lp, applicazioni in machine learning con regressione robusta.

Parametri di calcolo
Questo calcolatore ti è stato utile?

Distanza Manhattan (L1)

La distanza Manhattan (anche detta L1, taxicab o rectilinear) tra due punti A = (a_1, ..., a_n) e B = (b_1, ..., b_n) e definita come:

d_1(A, B) = sum_{i=1}^{n} |a_i - b_i|

Somma di valori assoluti delle differenze coordinate. E la distanza a piedi in una città a griglia perfetta come Manhattan (NYC), dove non si può tagliare diagonalmente attraverso gli edifici.

Origine: la griglia di Manhattan

Manhattan ha planimetria ortogonale: strade nord-sud (Avenues) e est-ovest (Streets). Camminando dal punto A = (3rd Ave, 5th St) al punto B = (5th Ave, 8th St) si percorre |5-3| = 2 blocchi a est più |8-5| = 3 blocchi a nord, totale 5 blocchi. Distanza Manhattan = 2 + 3 = 5. Diagonale euclidea sarebbe sqrt(13) = 3.6, ma non e percorribile a piedi.

Formule

  • 2D: d_1 = |x_2 - x_1| + |y_2 - y_1|.
  • 3D: d_1 = |x_2 - x_1| + |y_2 - y_1| + |z_2 - z_1|.
  • N-D: d_1 = sum |a_i - b_i|.

Geometria taxicab

Geometria con metrica L1 invece di L2. Sorprendentemente diversa:

  • Cerchi: insieme {x : ||x||_1 = r} forma un QUADRATO ruotato di 45 gradi (rombo) con vertici (r,0), (0,r), (-r,0), (0,-r).
  • Pi taxicab: rapporto perimetro/diametro di cerchio L1 = 4 (vs 3.14159... euclideo).
  • Triangoli: somma degli angoli interni può essere diversa da pi (no parallelo postulato).
  • Esistono triangoli "isosceli L1" che NON sono isosceli L2.

Confronto con Euclidea (L2)

Per A = (0, 0), B = (3, 4):

  • Manhattan (L1): 3 + 4 = 7
  • Euclidea (L2): sqrt(9 + 16) = 5
  • Chebyshev (Linf): max(3, 4) = 4

Disuguaglianza generale: ||x||_inf <= ||x||_2 <= ||x||_1 = della Euclidea (in R^2: rapporto fino a sqrt(2) ~ 1.414).

Robustezza agli outlier

L1 e Più ROBUSTA agli outlier rispetto a L2. Un singolo valore anomalo e penalizzato linearmente in L1, quadraticamente in L2. Esempio: vettori (1, 1, 1, 100) e (1, 1, 1, 0). L1 = 100, L2 = 100. Per (1, 1, 1, 100) e (2, 2, 2, 1): L1 = 102, L2 = sqrt(99^2 + 3) ~ 99.05. L1 enfatizza la differenza outlier più di L2.

Norme Lp e induzione di sparsita

La norma L1 nelle ottimizzazioni induce SPARSITA: la minimizzazione di funzione L1 + obiettivo tende a soluzioni con molte componenti uguali a zero. Esempi:

  • Lasso (Tibshirani 1996): regressione lineare con regolarizzazione L1.
  • L1-SVM: classificatore con regolarizzazione L1.
  • Compressed Sensing (Donoho-Tao-Candes 2006): recupero segnali sparsi da pochi campioni.
  • Total variation denoising: rimozione rumore preservando bordi.

Applicazioni

  • Robotica: pianificazione cammino su griglia (A* con distanza Manhattan come euristica).
  • Computer vision: edge detection, gradiente Sobel L1.
  • Machine Learning: regressione robusta, lasso, sparse models.
  • VLSI design: distanze di routing tra componenti.
  • Ricerca operativa: trasporto e logistica.
  • Bioinformatica: edit distance varianti.
  • Compressione: encoding differenziale.
  • Audio processing: spectral metrics.

Algoritmi correlati

Algoritmo A* su griglia rettangolare usa la distanza Manhattan come euristica AMMISSIBILE (non sopravvaluta mai il costo reale). Garantisce ottimo. Per griglie con movimenti diagonali consentiti: distanza Chebyshev. Per movimenti continui: Euclidea.

Cerchi taxicab e geometria non-euclidea

Nella geometria taxicab i "cerchi" sono rombi inclinati. Conseguenze sorprendenti: due cerchi possono intersecarsi in 0, 1, 2 o INFINITI punti (segmenti di sovrapposizione). Il teorema di Talete non vale in forma standard. La somma degli angoli interni di un triangolo può eccedere pi (eccesso angolare). Studio formale: Krause (1973), basato su geometrie metriche di Minkowski.

Manhattan generalizzata: Lp con p non intero

La famiglia di norme Lp si estende a p reale qualsiasi: ||x||_p = (sum |x_i|^p)^(1/p). Per 0 < p 0: norma "L0" (numero di componenti non zero), usata in compressed sensing.

Storia

Hermann Minkowski (1864-1909) studio geometrie metriche generali. Krause (1973) formalizza taxicab geometry. Tibshirani (1996) introduce Lasso con regolarizzazione L1. Donoho-Tao-Candes (2006) provano teorema fondamentale del compressed sensing: L1 minimization recupera vettori sparsi sotto ipotesi RIP.

Modalita del calcolatore

Cinque modalita: distanza 2D Manhattan, 3D Manhattan, N-dimensionale, confronto tra metriche L1, L2, L3, Linf, e proprietà geometria taxicab (cerchi e pi taxicab).

La scelta della metrica in machine learning

La distanza Manhattan non e solo una curiosita geometrica: la scelta fra L1 ed L2 influenza concretamente il comportamento degli algoritmi di apprendimento. Nel k-nearest neighbors e nel clustering k-means la metrica determina la forma dei vicinati e dei cluster. La distanza euclidea produce sfere, la Manhattan produce rombi allineati agli assi, e questo cambia quali punti vengono considerati simili, soprattutto quando le dimensioni hanno significati diversi.

Un fenomeno controintuitivo emerge in alta dimensione, la cosiddetta maledizione della dimensionalita: al crescere del numero di dimensioni le distanze euclidee tendono a concentrarsi, rendendo tutti i punti quasi equidistanti e poco informativi. Studi hanno mostrato che le norme con esponente piu basso, come L1 o addirittura le norme frazionarie con p minore di 1, preservano meglio il contrasto fra vicino e lontano. Per questo in contesti ad altissima dimensionalita la Manhattan e spesso preferita all'euclidea.

Manhattan nel mondo reale: VLSI, routing e logistica

La distanza Manhattan e la metrica naturale ovunque il movimento sia vincolato a una griglia. Nella progettazione di circuiti integrati (VLSI) le piste di collegamento corrono lungo direzioni ortogonali su strati sovrapposti: la lunghezza dei fili si stima proprio con la distanza Manhattan, e minimizzarla riduce ritardi e consumo. Gli algoritmi di routing su chip, come l'albero di Steiner rettilineo, ottimizzano interconnessioni misurate in questa metrica.

Lo stesso vale per la logistica e la robotica su griglia. I magazzini automatizzati muovono i robot lungo corsie ortogonali, e la distanza Manhattan stima il tempo di percorrenza meglio della linea retta. Negli algoritmi di ricerca del cammino, come A*, la distanza Manhattan e l'euristica ammissibile standard per griglie con movimenti solo orizzontali e verticali, garantendo di trovare il percorso ottimale. Dalla pianificazione urbana ai videogiochi a scacchiera, questa metrica descrive il costo reale del muoversi in un mondo a blocchi.

Aggiornato a luglio 2026

Domande frequenti

Cos'e la distanza di Manhattan?

E la distanza L1 fra due punti, calcolata come somma dei valori assoluti delle differenze delle coordinate: |x2-x1| + |y2-y1|. Rappresenta il percorso minimo in una citta a griglia, dove ci si muove solo lungo strade ortogonali, senza tagliare in diagonale.

Perche si chiama distanza di Manhattan?

Dal quartiere di Manhattan a New York, con la sua caratteristica griglia regolare di strade. Un taxi che va da un punto all'altro deve seguire le strade nord-sud ed est-ovest, percorrendo esattamente la distanza L1. Per questo e detta anche taxicab distance o city block distance.

Che differenza c'e con la distanza euclidea?

La distanza euclidea (L2) misura la linea retta fra due punti, radice della somma dei quadrati delle differenze. La Manhattan (L1) somma i valori assoluti. La Manhattan e sempre maggiore o uguale all'euclidea, fino a un fattore radice(n) in n dimensioni.

Cos'e la geometria taxicab?

E la geometria che usa la distanza Manhattan al posto dell'euclidea. In essa i "cerchi" (luoghi a distanza costante) sono quadrati ruotati di 45 gradi, il pi greco vale 4 anziche 3,14, e i triangoli hanno proprieta diverse. Introdotta didatticamente da Krause negli anni Settanta.

Perche la Manhattan e robusta agli outlier?

Perche somma i valori assoluti invece dei quadrati: un errore grande in una singola dimensione contribuisce linearmente, non quadraticamente. Cosi un punto anomalo influenza meno il risultato complessivo, rendendo la L1 preferibile quando i dati contengono valori estremi o rumore.

Perche la norma L1 induce sparsita?

Perche la sua palla unitaria e un rombo con i vertici sugli assi: nella minimizzazione le soluzioni tendono a "toccare" questi vertici, dove molte coordinate sono esattamente zero. E il principio del Lasso e del compressed sensing, che sfruttano L1 per ottenere modelli con pochi parametri non nulli.

Quando conviene usare Manhattan invece di Euclidea?

Quando il movimento e vincolato a una griglia (citta, circuiti, robot su corsie), quando i dati contengono outlier da attenuare, quando serve sparsita (Lasso), o in altissima dimensione, dove la L1 preserva meglio il contrasto fra distanze rispetto all'euclidea.

Dove si usa nella pratica?

In progettazione di circuiti VLSI per stimare la lunghezza dei fili, in robotica e logistica su griglia, nell'euristica dell'algoritmo A* per il pathfinding, nel machine learning (k-NN, clustering, regressione Lasso) e nei videogiochi a scacchiera. Ovunque il costo del movimento sia rettilineo.

Formula

Manhattan: d_1 = sum_{i=1}^{n} |a_i - b_i|. Generalizzazione Lp: d_p = (sum |a_i - b_i|^p)^(1/p). p=1 Manhattan/L1/taxicab, p=2 Euclidea, p=infty Chebyshev.

Commenti (0)

Ancora nessun commento. Sii il primo!