Manhattan Distanz (L₁-Norm)

Rechner zur Berechnung der Taxicab-Distanz mit ausführlichen Formeln und Beispielen

Manhattan Distanz Rechner

Was wird berechnet?

Die Manhattan Distanz (auch Taxicab-Distanz oder L₁-Norm genannt) ist die Summe der absoluten Differenzen aller Komponenten. Sie entspricht der Distanz entlang von Gitterlinien.

Eingabepunkte/Vektoren

Koordinaten durch Leerzeichen getrennt

Gleiche Anzahl Koordinaten wie X

Ergebnis
Manhattan Distanz (L₁):
Summe der absoluten Differenzen (Gitterdistanz)

Manhattan Info

Eigenschaften

Manhattan Distanz:

  • Auch L₁-Norm oder Taxicab-Distanz
  • Summe absoluter Differenzen
  • Folgt rechtwinkligen Pfaden
  • Robust gegen Ausreißer

Intuition: Die Distanz, die ein Taxi in Manhattan zurücklegen muss, wenn es nur entlang von Straßen fahren kann.

Spezielle Fälle
2D Stadtblöcke:
|Δx| + |Δy| = Anzahl Blöcke
Diamant-Form:
Einheitskugel ist Diamant/Raute
Median-Minimierung:
Minimiert Summe absoluter Abweichungen
Verwandte Normen

→ Euklidische Distanz (L₂)
→ Chebyshev Distanz (L∞)
→ Minkowski Distanz (Lₚ)

Formeln der Manhattan Distanz

Grundformel (L₁-Norm)
\[d_1(x,y) = \sum_{i=1}^n |x_i - y_i|\] Standard Manhattan Distanz
Vektornorm
\[d_1(x,y) = \|x-y\|_1\] L₁-Norm der Differenz
2D-Formel (Taxicab)
\[d = |x_2-x_1| + |y_2-y_1|\] Klassische Taxicab-Distanz
3D-Formel (Raum)
\[d = |x_2-x_1| + |y_2-y_1| + |z_2-z_1|\] Erweiterte Manhattan-Distanz
Gewichtete Form
\[d_w(x,y) = \sum_{i=1}^n w_i |x_i - y_i|\] Mit Gewichten wᵢ
Median-Beziehung
\[\text{arg min}_c \sum_{i=1}^n |x_i - c| = \text{median}(x)\] Median minimiert L₁-Norm

Detailliertes Rechenbeispiel

Beispiel: Manhattan([3,4,5], [2,3,6]) berechnen

Gegeben:

  • Punkt A = [3, 4, 5]
  • Punkt B = [2, 3, 6]

Schritt 1 - Absolute Differenzen:

  • |3 - 2| = 1
  • |4 - 3| = 1
  • |5 - 6| = 1

Schritt 2 - Summe:

\[d_1 = 1 + 1 + 1 = 3\]

Interpretation: Die Manhattan-Distanz entspricht der Anzahl "Schritte" entlang der Koordinatenachsen.

Taxicab-Visualisierung

Beispiel: Von (1,1) nach (4,3) in Manhattan

Gittervisualisierung:

E
↑ →
S → →

Ein möglicher Pfad: 3 rechts + 2 hoch = 5 Schritte

Berechnung:

\[d_1 = |4-1| + |3-1| = 3 + 2 = 5\]

Alle möglichen Pfade:

  • 3× rechts, dann 2× hoch
  • 2× hoch, dann 3× rechts
  • Beliebige Kombination von 3R + 2H
  • Alle haben Länge 5!

Vergleich der Lₚ-Normen

Für die Punkte [0,0] und [3,4]
L₁ (Manhattan)
7.000

|3| + |4| = 7

L₂ (Euklidisch)
5.000

√(3² + 4²) = 5

L₃ (Minkowski)
4.498

(3³ + 4³)^(1/3)

L∞ (Chebyshev)
4.000

max(3, 4) = 4

Beobachtung: Manhattan gibt die größte Distanz, da keine "Abkürzungen" diagonal möglich sind.

Praktische Anwendungen

Stadtplanung & Navigation
  • Stadtblock-Distanzen
  • Taxifahrten in Rasterstraßen
  • Logistik-Optimierung
  • Fußgänger-Navigation
Machine Learning
  • k-Nearest Neighbors
  • Clustering (robuster gegen Ausreißer)
  • Feature Selection
  • Sparse Data Analysis
Statistik & Optimierung
  • Median-Berechnung
  • Robuste Regression
  • LASSO-Regularisierung
  • Quantile Regression

Mathematische Eigenschaften

Norm-Eigenschaften
  • Positivität: ‖x‖₁ ≥ 0, ‖x‖₁ = 0 ⟺ x = 0
  • Homogenität: ‖αx‖₁ = |α|‖x‖₁
  • Dreiecksungleichung: ‖x+y‖₁ ≤ ‖x‖₁ + ‖y‖₁
  • Dual zur L∞-Norm: Hölder-Konjugation
Geometrische Eigenschaften
  • Einheitskugel: Oktaeder (3D), Diamant (2D)
  • Konvex: Aber nicht strikt konvex
  • Polyedrisch: Einheitskugel ist Polytop
  • Nicht differenzierbar: An Koordinatenachsen
Beziehungen zu anderen Normen

Zu L₂-Norm:
‖x‖₂ ≤ ‖x‖₁ ≤ √n ‖x‖₂

Zu L∞-Norm:
‖x‖∞ ≤ ‖x‖₁ ≤ n ‖x‖∞

Robustheit gegen Ausreißer

Vergleich: Median vs. Mittelwert

Daten ohne Ausreißer:

Datenpunkte: [1, 2, 3, 4, 5]
Mittelwert (L₂): 3.0
Median (L₁): 3.0
Beide gleich

Daten mit Ausreißer:

Datenpunkte: [1, 2, 3, 4, 100]
Mittelwert (L₂): 22.0
Median (L₁): 3.0
Median bleibt stabil!

Fazit: Die L₁-Norm (Manhattan) ist robuster gegen Ausreißer, da sie das Median-Prinzip verwendet, welches weniger empfindlich auf extreme Werte reagiert.

Algorithmische Aspekte

Effizienz und Implementierung

Zeitkomplexität:

  • Berechnung: O(n) linear
  • k-NN Suche: O(n·m) für m Punkte
  • Median-Suche: O(n log n)
  • Vorteil: Keine Quadrierung/Wurzel

Numerische Stabilität:

  • Overflow-resistent: Nur Addition
  • Ganzzahlig: Exakt für Integer
  • Monoton: Keine Oszillationen
  • Sparse-freundlich: Viele Nullen bleiben

Distanz Funktionen

Bray Curtis Distanz  •  Canberra Distanz  •  Euklidischer Abstand  •  Korrelationskoeffizient  •  Kosinus Ähnlichkeit  •  Levenshtein Distanz  •  Manhattan Distanz  •  Minkowski Distanz  •  Maximumsnorm  •