Taxi -Geometrie

Taxi -Geometrie gegen euklidische Entfernung: In der Taxi -Geometrie haben die roten, gelben, blauen und grünen Pfade die gleichen kürzester Weg Länge von 12. In der euklidischen Geometrie hat die grüne Linie eine Länge

{\ displayStyle 6 {\ sqrt {2}} \ ca. 8.49}

und ist der einzigartige kürzeste Weg, während die anderen Pfade die längere Länge von 12 haben.

A Taxi -Geometrie ist eine Form von Geometrie in denen die übliche Entfernungsfunktion oder metrisch von Euklidische Geometrie wird durch eine neue Metrik ersetzt, in der die Distanz Zwischen zwei Punkten ist die Summe der Absolute Unterschiede ihrer Kartesischen Koordinaten. Das Taxi -Metrik ist auch bekannt als als geradlinige Entfernung, L₁ Distanz, L¹ Distanz oder ${\ displayStyle \ ell _ {1}}$ Norm (sehen L^p Platz), Schlange Distanz, Stadtblockentfernung, Manhattan -Entfernung oder Manhattan Länge, mit entsprechenden Variationen im Namen der Geometrie.^[1] Die letzteren Namen verweisen auf die Gitterlayout der meisten Straßen auf der Insel von Manhattan, was den kürzesten Weg verursacht, den ein Auto zwischen zwei Kreuzungen in der einnehmen kann Bezirk Länge entsprechen der Entfernung der Kreuzungen in der Taxi -Geometrie.

Die Geometrie wurde in verwendet Regressionsanalyse seit dem 18. Jahrhundert und heute oft als als bezeichnet LASSO. Die geometrische Interpretation stammt aus Nichteuklidische Geometrie des 19. Jahrhunderts und ist geschehen Hermann Minkowski.

In zwei Dimensionen der Taxi -Abstand zwischen zwei Punkten ${\ displayStyle (x_ {1}, y_ {1})}$ und ${\ displayStyle (x_ {2}, y_ {2})}$ ist ${\ displaystyle \ links | x_ {1} -x_ {2} \ rechts |+\ links | y_ {1} -y_ {2} \ rechts |}$ . Das heißt, es ist die Summe der absoluten Werte der Unterschiede zwischen beiden Koordinatensätzen.

Formale Definition

Die Taxi -Distanz, ${\ displayStyle d_ {1}}$ zwischen zwei Vektoren ${\ displaystyle \ mathbf {p}, \ mathbf {q}}$ in einem (n n-Dimensional real Vektorraum mit fest Kartesisches Koordinatensystem, ist die Summe der Längen der Projektionen der Liniensegment zwischen den Punkten auf die Koordinatenachsen. Formeller,

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

wo

{\ displayStyle (\ mathbf {p}, \ mathbf {q})}

sind Vektoren

oder }, \ dots, q_ {n})}

Zum Beispiel in der Flugzeug, die Taxi -Distanz zwischen ${\ displayStyle (p_ {1}, p_ {2})}$ und ${\ displayStyle (q_ {1}, q_ {2})}$ ist ${\ displaystyle \ links | P_ {1} -q_ {1} \ rechts |+\ links | p_ {2} -q_ {2} \ rechts |.}$

Eigenschaften

Taxi -Distanz hängt von der ab Drehung des Koordinatensystems, hängt aber nicht von seiner ab Betrachtung über eine Koordinatenachse oder ihre Übersetzung. Taxi -Geometrie erfüllt alle Hilberts Axiome (eine Formalisierung von Euklidische Geometrie) mit Ausnahme der Seitenwinkel-Seite Axiom, wie zwei Dreiecke mit gleichermaßen "langen" zwei Seiten und ein identischer Winkel zwischen ihnen sind typischerweise nicht kongruent Es sei denn, die genannten Seiten sind parallel.

Bälle

Kreise in der diskreten und kontinuierlichen Taxi -Geometrie

A Topologischer Ball ist eine Reihe von Punkten mit fester Entfernung, die als die genannt Radius, von einem Punkt namens das namens das Center. Im n-Dimensionale euklidische Geometrie, die Bälle sind Kugeln. In der Taxi -Geometrie wird die Entfernung durch eine andere Metrik bestimmt als bei der euklidischen Geometrie, und die Form der Kugeländerung. Im n Dimensionen, ein Taxi -Ball ist in Form eines n-Dimensional Orthoplex. In zwei Dimensionen sind diese Quadrate mit den Seiten, die in einem Winkel von 45 ° zu den Koordinatenachsen ausgerichtet sind. Das Bild rechts zeigt, warum dies wahr ist, indem sie den Satz aller Punkte mit einem festen Abstand von einem in Blau dargestellten Mitte zeigt. Wenn die Größe der Stadtblöcke abnimmt, werden die Punkte zahlreicher und werden zu einem gedrehten Quadrat in einer kontinuierlichen Taxi -Geometrie. Während jede Seite Länge hätte ${\ displayStyle {\ sqrt {2}} r}$ Verwendung einer Euklidische Metrik, wo r ist der Radius des Kreises, seine Länge in der Taxi -Geometrie beträgt 2r. Somit beträgt der Umfang eines Kreises 8r. Somit der Wert eines geometrischen Analogon zu ${\ displayStyle \ pi}$ ist 4 in dieser Geometrie. Die Formel für den Einheitskreis in der Taxi -Geometrie ist ${\ displayStyle | x |+| y | = 1}$ in Kartesischen Koordinaten und

{\ displayStyle r = {\ frac {1} {\ links | \ sin \ theta \ rechts |+\ links | \ cos \ theta \ rechts |}}}

in Polar Koordinaten.

Ein Kreis von Radius 1 (unter Verwendung dieser Entfernung) ist der Von Neumann Viertel von seinem Zentrum.

Ein Radiuskreis r für die Chebyshev Distanz (L_∞ metrisch) auf einer Ebene ist auch ein Quadrat mit Seitenlänge 2r Parallel zu den Koordinatenachsen kann der planare Chebyshev -Entfernung als äquivalent durch Rotation und Skalierung der planaren Taxi -Distanz angesehen werden. Diese Äquivalenz zwischen l₁ und ich_∞ Metriken verallgemeinern nicht auf höhere Dimensionen.

Immer wenn jedes Paar in einer Sammlung dieser Kreise einen nicht leeren Schnittpunkt hat, gibt es einen Schnittpunkt für die gesamte Sammlung; Daher bildet die Manhattan -Entfernung eine Injektiv metrischer Raum.

Anwendungen

Komprimierte Erfindung

Bei der Lösung von unterbestimmtes System von linearen Gleichungen die Regulierung Der Term für den Parametervektor wird in Bezug auf das ausgedrückt ${\ displayStyle \ ell _ {1}}$ -norm (Taxi -Geometrie) des Vektors.^[2] Dieser Ansatz erscheint im Signalwiederherstellungsrahmen genannt Komprimierte Erfindung.

Unterschiede zu Frequenzverteilungen

Die Taxi -Geometrie kann verwendet werden, um die Unterschiede in der diskreten Frequenzverteilung zu bewerten. Zum Beispiel in RNA -Spleißen Positionsverteilungen von Hexamer, die die Wahrscheinlichkeit eines jeden Hexamers zeichnen, der jeweils angegeben ist Nukleotid In der Nähe einer Spleißstelle kann mit der L1-Distanz verglichen werden. Jede Positionsverteilung kann als Vektor dargestellt werden, bei dem jeder Eintrag die Wahrscheinlichkeit darstellt, dass der Hexamer an einem bestimmten Nukleotid beginnt. Eine große L1-Distanz zwischen den beiden Vektoren weist auf einen signifikanten Unterschied in der Art der Verteilungen hin, während ein kleiner Abstand ähnlich geformte Verteilungen bezeichnet. Dies entspricht der Messung der Fläche zwischen den beiden Verteilungskurven, da die Fläche jedes Segments die absolute Differenz zwischen den Wahrscheinlichkeiten der beiden Kurven an diesem Punkt ist. Wenn es für alle Segmente zusammen summiert wird, liefert es das gleiche Maß wie die L1-Distanz.^[3]

Geschichte

Das L¹ Metrik wurde in verwendet Regressionsanalyse 1757 von Roger Joseph Boscovich.^[4] Die geometrische Interpretation stammt aus dem späten 19. Jahrhundert und die Entwicklung von Nichteuklidische Geometrien, insbesondere von Hermann Minkowski und sein Minkowski -Ungleichheit, von denen diese Geometrie ein Sonderfall ist, insbesondere in der Geometrie der Zahlen, (Minkowski 1910). Die Formalisierung von L^p Räume wird angeschrieben (Riesz 1910).

Siehe auch

Fünfzehn Puzzle
Hamming -Entfernung- Anzahl der Bits, die zwischen zwei Saiten unterscheiden
Manhattan Verkabelung
Mannheim -Entfernung
Metrisch- Mathematische Funktion definieren Distanz
Minkowski -Entfernung
Normed Vektorraum- Vektorraum, auf dem eine Entfernung definiert ist
Orthogonaler konvexer Rumpf-minimales Superset, die jede Achse-Parallel-Linie in einem Intervall schneidet
Zielloser Spaziergang- Mathematische Formalisierung eines Pfades, der aus einer Folge zufälliger Schritte besteht

Anmerkungen

^ Schwarz, Paul E. "Manhattan Distanz". Wörterbuch von Algorithmen und Datenstrukturen. Abgerufen 6. Oktober, 2019.
^ Donoho, David L. (23. März 2006). "Für die meisten großen unterbestimmten Systeme der linearen Gleichungen die minimale ${\ displayStyle \ ell _ {1}}$ -Norm -Lösung ist auch die spärlichste Lösung. " Communications on Pure and Applied Mathematics. 59 (6): 797–829. doi:10.1002/cpa.20132.
^ Lim, Kian Huat; Ferraris, Luciana; Filloux, Madeleine E.; Raphael, Benjamin J.; Fairbrother, William G. (5. Juli 2011). "Verwenden der Positionsverteilung, um Spleißelemente zu identifizieren und prä-mRNA-Verarbeitungsdefekte in menschlichen Genen vorherzusagen". Verfahren der Nationalen Akademie der Wissenschaften der Vereinigten Staaten von Amerika. 108 (27): 11093–11098. Bibcode:2011pnas..10811093h. doi:10.1073/pnas.1101135108. PMC 3131313. PMID 21685335.
^ Stigler, Stephen M. (1986). Die Geschichte der Statistik: Die Messung der Unsicherheit vor 1900. Harvard University Press. ISBN 9780674403406. Abgerufen 6. Oktober, 2019.

Verweise

Krause, Eugene F. (1987). Taxi -Geometrie. Dover. ISBN 978-0-486-25202-5.
Minkowski, Hermann (1910). Geometrie der Zahlen (auf Deutsch). Leipzig und Berlin: R. G. Teubner. JFM 41.0239.03. HERR 0249269. Abgerufen 6. Oktober, 2019.
Riesz, Frigyes (1910). "Intersuchungen über Systeme Integrierbarer Funktionen". Mathematische Annalen (auf Deutsch). 69 (4): 449–497. doi:10.1007/bf01457637. HDL:10338.DMLCZ/128558. S2CID 120242933.

Externe Links

Weisstein, Eric W. "Taxicab Metrik". Mathord.
Malkevitch, Joe (1. Oktober 2007). "Taxi!". American Mathematical Society. Abgerufen 6. Oktober, 2019.

[1] Schwarz, Paul E. "Manhattan Distanz". Wörterbuch von Algorithmen und Datenstrukturen. Abgerufen 6. Oktober, 2019.

[2] Donoho, David L. (23. März 2006). "Für die meisten großen unterbestimmten Systeme der linearen Gleichungen die minimale ${\ displayStyle \ ell _ {1}}$ -Norm -Lösung ist auch die spärlichste Lösung. " Communications on Pure and Applied Mathematics. 59 (6): 797–829. doi:10.1002/cpa.20132.

[lim-3] Lim, Kian Huat; Ferraris, Luciana; Filloux, Madeleine E.; Raphael, Benjamin J.; Fairbrother, William G. (5. Juli 2011). "Verwenden der Positionsverteilung, um Spleißelemente zu identifizieren und prä-mRNA-Verarbeitungsdefekte in menschlichen Genen vorherzusagen". Verfahren der Nationalen Akademie der Wissenschaften der Vereinigten Staaten von Amerika. 108 (27): 11093–11098. Bibcode:2011pnas..10811093h. doi:10.1073/pnas.1101135108. PMC 3131313. PMID 21685335.

[Stigler1986-4] Stigler, Stephen M. (1986). Die Geschichte der Statistik: Die Messung der Unsicherheit vor 1900. Harvard University Press. ISBN 9780674403406. Abgerufen 6. Oktober, 2019.

[1]

[2]

[3]

[4]