View source for Taxicab geometry

{{Short description|Type of metric geometry}}
[[File:Manhattan distance.svg|thumb|upright=1.2|In taxicab geometry, the lengths of the red, blue, green, and yellow paths all equal {{math|12}}, the taxicab distance between the opposite corners, and all four paths are shortest paths. Instead, in Euclidean geometry, the red, blue, and yellow paths still have length {{math|12}} but the green path is the unique shortest path, with length equal to the Euclidean distance between the opposite corners, {{math|6√2 ≈ 8.49}}.]]

'''Taxicab geometry''' or '''Manhattan geometry''' is [[geometry]] where the familiar [[Euclidean distance]] is ignored, and the [[distance]] between two [[point (geometry)|points]] is instead defined to be the sum of the [[absolute difference]]s of their respective [[Cartesian coordinate]]s, a distance function (or [[Metric (mathematics)|metric]]) called the ''taxicab distance'', ''Manhattan distance'', or ''city block distance''. The name refers to the island of [[Manhattan]], or generically any planned city with a [[rectangular grid]] of streets, in which a taxicab can only travel along grid directions. In taxicab geometry, the distance between any two points equals the length of their shortest grid path. This different definition of distance also leads to a different definition of the length of a curve, for which a [[line segment]] between any two points has the same length as a grid path between those points rather than its Euclidean length.

The taxicab distance is also sometimes known as ''rectilinear distance'' or {{math|''L''<sup>1</sup>}} distance (see [[Lp space|''L<sup>p</sup>'' space]]).<ref>{{cite web |last=Black |first=Paul E. |title=Manhattan distance |url=https://xlinux.nist.gov/dads/HTML/manhattanDistance.html |access-date=October 6, 2019 |work=Dictionary of Algorithms and Data Structures}}</ref> This geometry has been used in [[regression analysis]] since the 18th century, and is often referred to as [[Lasso (statistics)|LASSO]]. Its geometric interpretation dates to [[non-Euclidean geometry]] of the 19th century and is due to [[Hermann Minkowski]].

In the two-[[dimension]]al [[real coordinate space]] <math>\R^2</math>, the taxicab distance between two points <math>(x_1, y_1)</math> and <math>(x_2, y_2)</math> is <math>\left|x_1 - x_2\right| + \left|y_1 - y_2\right|</math>. That is, it is the sum of the [[absolute value]]s of the differences in both coordinates.

== Formal definition ==
The taxicab distance, <math>d_\text{T}</math>, between two points <math>\mathbf{p} = (p_1, p_2, \dots, p_n) \text{ and } \mathbf{q} = (q_1, q_2, \dots, q_n)</math> in an ''n''-dimensional [[real coordinate space]] with fixed [[Cartesian coordinate system]], is the sum of the lengths of the projections of the [[line segment]] between the points onto the [[coordinate axes]].  More formally,<math display="block">d_\text{T}(\mathbf{p}, \mathbf{q}) = \left\|\mathbf{p} - \mathbf{q}\right\|_\text{T} = \sum_{i=1}^n \left|p_i - q_i\right|</math>For example, in <math>\mathbb{R}^2
</math>, the taxicab distance between <math>\mathbf{p} = (p_1,p_2)</math> and <math>\mathbf{q} = (q_1,q_2)</math> is <math>\left| p_1 - q_1 \right| + \left| p_2 - q_2 \right|.</math>

== History ==
The ''L''<sup>1</sup> metric was used in [[regression analysis]], as a measure of [[goodness of fit]], in 1757 by [[Roger Joseph Boscovich]].<ref name="Stigler19862">{{cite book |last=Stigler |first=Stephen M. |url=https://archive.org/details/historyofstatist00stig |title=The History of Statistics: The Measurement of Uncertainty before 1900 |publisher=Harvard University Press |year=1986 |isbn=9780674403406 |access-date=October 6, 2019 |url-access=registration}}</ref> The interpretation of it as a distance between points in a geometric space dates to the late 19th century and the development of [[non-Euclidean geometries]]. Notably it appeared in 1910 in the works of both [[Frigyes Riesz]] and [[Hermann Minkowski]]. The formalization of [[Lp space|''L''<sup>p</sup> spaces]], which include taxicab geometry as a special case, is credited to Riesz.<ref>{{cite journal |last=Riesz |first=Frigyes |author-link=Frigyes Riesz |year=1910 |title=Untersuchungen über Systeme integrierbarer Funktionen |url=https://zenodo.org/record/2456593 |journal=Mathematische Annalen |language=de |volume=69 |issue=4 |pages=449–497 |doi=10.1007/BF01457637 |hdl-access=free |hdl=10338.dmlcz/128558 |s2cid=120242933}}</ref> In developing the [[geometry of numbers]], [[Hermann Minkowski]] established his [[Minkowski inequality]], stating that these spaces define [[normed vector space]]s.<ref>{{cite book |last=Minkowski |first=Hermann |url=https://archive.org/details/geometriederzahl00minkrich |title=Geometrie der Zahlen |publisher=R. G. Teubner |year=1910 |location=Leipzig and Berlin |language=de |jfm=41.0239.03 |mr=0249269 |author-link=Hermann Minkowski |access-date=October 6, 2019}}</ref>

The name ''taxicab geometry'' was introduced by [[Karl Menger]] in a 1952 booklet ''You Will Like Geometry'', accompanying a geometry exhibit intended for the general public at the [[Museum of Science and Industry (Chicago)|Museum of Science and Industry]] in Chicago.<ref>{{citation |mode=cs1 |last=Menger |first=Karl |title= You Will Like Geometry. A Guide Book for the Illinois Institute of Technology Geometry Exhibition |year=1952 |publisher=Museum of Science and Industry |place=Chicago }} {{pb}} {{cite journal |last=Golland |first=Louise |year=1990 |title=Karl Menger and Taxicab Geometry |journal=Mathematics Magazine |volume=63 |number=5 |pages=326–327 |doi=10.1080/0025570x.1990.11977548}}</ref>

== Properties ==
Thought of as an additional structure layered on [[Euclidean space]], taxicab distance depends on the [[Orientation (geometry)|orientation]] of the coordinate system and is changed by Euclidean [[rotation]] of the space, but is unaffected by [[translation (geometry)|translation]] or axis-aligned [[Reflection (mathematics)|reflection]]s. Taxicab geometry satisfies all of [[Hilbert's axioms]] (a formalization of [[Euclidean geometry]]) except that the congruence of angles cannot be defined to precisely match the Euclidean concept, and under plausible definitions of congruent taxicab angles, the [[Congruence (geometry)#Determining congruence|side-angle-side axiom]] is not satisfied as in general triangles with two taxicab-congruent sides and a taxicab-congruent angle between them are  not [[Congruence (geometry)#Congruence of triangles|congruent triangles]].

=== Spheres ===
[[File:TaxicabGeometryCircle.svg|thumb|upright=0.8|Grid points on a circle in taxicab geometry as the grid is made finer]]

In any [[metric space]], a [[Sphere#Metric spaces|sphere]] is a set of points at a fixed distance, the ''[[radius]]'', from a specific ''[[Centre (geometry)|center]]'' point. Whereas a Euclidean sphere is round and rotationally symmetric, under the taxicab distance, the shape of a sphere is a [[cross-polytope]], the ''n''-dimensional generalization of a [[regular octahedron]], whose points <math>\mathbf{p}</math> satisfy the equation:

:<math>d_\text{T}(\mathbf p, \mathbf c) = \sum_{i=1}^n |p_i - c_i| = r,</math>

where <math>\mathbf{c}</math> is the center and ''r'' is the radius. Points <math>\mathbf{p}</math> on the [[unit sphere]], a sphere of radius 1 centered at the [[origin (mathematics)|origin]], satisfy the equation <math display=inline>d_\text{T}(\mathbf p, \mathbf 0) = \sum_{i=1}^n |p_i| = 1.</math>

In two dimensional taxicab geometry, the sphere (called a ''[[circle]]'') is a [[square]] oriented diagonally to the coordinate axes. The image to the right shows in red the set of all points on a square grid with a fixed distance from the blue center. As the grid is made finer, the red points become more numerous, and in the limit tend to a continuous tilted square. Each side has taxicab length 2''r'', so the [[circumference]] is 8''r''. Thus, in taxicab geometry, the value of the analog of the circle constant [[pi|π]], the ratio of circumference to [[diameter]], is equal to 4. 

A closed ''[[ball (mathematics)#In general metric spaces|ball]]'' (or closed ''[[disk (mathematics)|disk]]'' in the 2-dimensional case) is a filled-in sphere, the set of points at distance less than or equal to the radius from a specific center. For [[cellular automata]] on a square grid, a taxicab [[disk (mathematics)|disk]] is the [[von Neumann neighborhood]] of range ''r'' of its center.

A circle of radius ''r'' for the [[Chebyshev distance]] ([[Lp space|L<sub>∞</sub> metric]]) on a plane is also a square with side length 2''r'' parallel to the coordinate axes, so planar Chebyshev distance can be viewed as equivalent by rotation and scaling to planar taxicab distance. However, this equivalence between L<sub>1</sub> and L<sub>∞</sub> metrics does not generalize to higher dimensions.

Whenever each pair in a collection of these circles has a nonempty intersection, there exists an intersection point for the whole collection; therefore, the Manhattan distance forms an [[injective metric space]].

=== Arc length ===
Let <math>y = f(x)</math> be a [[Differentiable function|continuously differentiable]] function. Let <math>s</math> be the taxicab [[arc length]] of the [[graph of a function|graph]] of <math>f</math> on some interval <math>[a,b]</math>. Take a [[partition of an interval|partition]] of the interval into equal infinitesimal subintervals, and let <math>\Delta s_i</math> be the taxicab length of the <math>i^{\text{th}}</math> subarc.  Then<ref>{{Cite book |last=Heinbockel |first=J.H. |title=Introduction to Calculus Volume II |publisher=Old Dominion University |year=2012 |pages=54–55}}</ref>

<math display="block">\Delta s_i = \Delta x_i + \Delta y_i = \Delta x_i+ |f(x_i) - f(x_{i-1})|.</math>

By the [[mean value theorem]], there exists some point <math>x^*_i</math> between <math>x_i </math> and <math>x_{i-1} </math> such that <math>f(x_i) - f(x_{i-1}) = f'(x^*_i)dx_i</math>.<ref>{{Cite journal |last=Penot |first=J.P. |date=1988-01-01 |title=On the mean value theorem |url=https://doi.org/10.1080/02331938808843330 |journal=Optimization |volume=19 |issue=2 |pages=147–156 |doi=10.1080/02331938808843330 |issn=0233-1934}}</ref>  Then the previous equation can be written

<math display="block">\Delta s_i = \Delta x_i + |f'(x^*_i)|\Delta x_i = \Delta x_i(1+|f'(x^*_i)|).</math>

Then <math>s </math> is given as the sum of every partition of <math>s </math> on <math>[a,b]</math> as they get [[Arbitrarily large|arbitrarily small]].[[File:Three_monotone_increasing_or_decreasing_curves_with_same_endpoints.png|thumb|221x221px|Curves defined by monotone increasing or decreasing functions have the same taxicab arc length as long as they share the same endpoints.]]<math>\begin{align}
s &= \lim_{n \rightarrow \infty} \sum_{i=1}^{n} \Delta x_i(1+|f'(x^*_i)|) \\
& = \int_{a}^{b} 1+|f'(x)| \,dx
\end{align} </math>
To test this, take the taxicab circle of [[radius]] <math>r </math> centered at the origin. Its curve in the first [[Quadrant (plane geometry)|quadrant]] is given by <math>f(x)=-x+r </math> whose length is

<math display="block">s = \int_{0}^{r} 1+|-1|dx = 2r </math>

Multiplying this value by <math>4 </math> to account for the remaining quadrants gives <math>8r </math>, which agrees with the [[circumference]] of a taxicab circle.<ref>{{Cite conference |last1=Petrović |first1=Maja |last2=Malešević |first2=Branko |last3=Banjac |first3=Bojan |last4=Obradović |first4=Ratko |year=2014 |title=Geometry of some taxicab curves |conference= 4th International Scientific Conference on Geometry and Graphics |publisher=Serbian Society for Geometry and Graphics, University of Niš, Srbija |arxiv=1405.7579}}</ref> Now take the [[Euclidean geometry|Euclidean]] circle of radius <math>r </math> centered at the origin, which is given by <math>f(x) = \sqrt{r^2-x^2} </math>. Its arc length in the first quadrant is given by

<math display="block">\begin{align}
s &= \int_{0}^{r} 1+|\frac{-x}{\sqrt{r^2 - x^2}}|dx\\
&= x+\sqrt{r^2-x^2} \bigg|^{r}_{0}\\
&= r-(-r)\\
&= 2r
\end{align} </math>

Accounting for the remaining quadrants gives <math>4 \times 2r = 8r </math> again. Therefore, the [[circumference]] of the taxicab circle and the [[Euclidean geometry|Euclidean]] circle in the taxicab [[Metric space|metric]] are equal.<ref>{{Cite thesis |last=Kemp |first=Aubrey |year=2018 |type=PhD thesis |title=Generalizing and Transferring Mathematical Definitions from Euclidean to Taxicab Geometry |publisher=Georgia State University |doi=10.57709/12521263 |doi-access=free }}</ref> In fact, for any function <math>f</math> that is monotonic and [[Differentiable function|differentiable]] with a continuous [[derivative]] over an interval <math>[a,b]</math>, the arc length of <math>f</math> over <math>[a, b]</math> is <math>(b-a) + \mid f(b)-f(a) \mid</math>.<ref>{{Cite journal |last=Thompson |first=Kevin P. |year=2011 |title=The Nature of Length, Area, and Volume in Taxicab Geometry |journal= International Electronic Journal of Geometry |volume=4 |number=2 |pages=193–207 |url=https://dergipark.org.tr/en/pub/iejg/issue/47488/599514 |arxiv=1101.2922}}</ref>

=== Triangle congruence ===
[[File:Congruencetriangletaxicab.png|thumb|391x391px|Two taxicab right isoceles triangles. Three angles and two legs are congruent, but the triangles are not congruent. Therefore, ASASA is not a congruence theorem in taxicab geometry.]]

Two triangles are congruent if and only if three corresponding sides are equal in distance and three corresponding angles are equal in measure. There are several theorems that guarantee [[Congruence (geometry)|triangle congruence]] in Euclidean geometry, namely Angle-Angle-Side (AAS), Angle-Side-Angle (ASA), Side-Angle-Side (SAS), and Side-Side-Side (SSS). In taxicab geometry, however, only SASAS guarantees triangle congruence.<ref>{{Cite journal |last=Mironychev |first=Alexander |date=2018 |title=SAS and SSA Conditions for Congruent Triangles |journal=Journal of Mathematics and System Science |volume=8 |issue=2 |pages=59–66}}</ref>

Take, for example, two right isosceles taxicab triangles whose angles measure 45-90-45. The two legs of both triangles have a taxicab length 2, but the [[hypotenuse]]s are not congruent. This counterexample eliminates AAS, ASA, and SAS. It also eliminates AASS, AAAS, and even ASASA. Having three congruent angles and two sides does not guarantee triangle congruence in taxicab geometry. Therefore, the only triangle congruence theorem in taxicab geometry is SASAS, where all three corresponding sides must be congruent and at least two corresponding angles must be congruent.<ref>{{Cite journal |last1=THOMPSON |first1=KEVIN |last2=DRAY |first2=TEVIAN |title=Taxicab Angles and Trigonometry |date=2000 |url=https://www.jstor.org/stable/24340535 |journal=Pi Mu Epsilon Journal |volume=11 |issue=2 |pages=87–96 |jstor=24340535 |issn=0031-952X}}</ref> This result is mainly due to the fact that the length of a line segment depends on its orientation in taxicab geometry.

== Applications ==

=== Compressed sensing ===
In solving an [[underdetermined system]] of linear equations, the [[Regularization (mathematics)|regularization]] term for the parameter vector is expressed in terms of the <math>\ell_1</math> norm (taxicab geometry) of the vector.<ref>{{cite journal |last=Donoho |first=David L. |date=March 23, 2006 |title=For most large underdetermined systems of linear equations the minimal <math>\ell_1</math>-norm solution is also the sparsest solution |journal=Communications on Pure and Applied Mathematics |volume=59 |issue=6 |pages=797–829 |doi=10.1002/cpa.20132|s2cid=8510060 }}</ref> This approach appears in the signal recovery framework called [[compressed sensing]].

=== Differences of frequency distributions ===
Taxicab geometry can be used to assess the differences in discrete frequency distributions. For example, in [[RNA splicing]] positional distributions of [[hexamers]], which plot the probability of each hexamer appearing at each given [[nucleotide]] near a splice site, can be compared with L1-distance. Each position distribution can be represented as a vector where each entry represents the likelihood of the hexamer starting at a certain nucleotide. A large L1-distance between the two vectors indicates a significant difference in the nature of the distributions while a small distance denotes similarly shaped distributions. This is equivalent to measuring the area between the two distribution curves because the area of each segment is the absolute difference between the two curves' likelihoods at that point. When summed together for all segments, it provides the same measure as L1-distance.<ref name="lim2">{{cite journal |last1=Lim |first1=Kian Huat |last2=Ferraris |first2=Luciana |last3=Filloux |first3=Madeleine E. |last4=Raphael |first4=Benjamin J. |last5=Fairbrother |first5=William G. |date=July 5, 2011 |title=Using positional distribution to identify splicing elements and predict pre-mRNA processing defects in human genes |journal=Proceedings of the National Academy of Sciences of the United States of America |volume=108 |issue=27 |pages=11093–11098 |bibcode=2011PNAS..10811093H |doi=10.1073/pnas.1101135108 |pmc=3131313 |pmid=21685335 |doi-access=free}}</ref>

== See also ==
[[File:Minkowski_distance_examples.svg|thumb|Comparison of Chebyshev, Euclidean and taxicab distances for the hypotenuse of a 3-4-5 triangle on a chessboard]]
* [[Chebyshev distance]]
* [[Hamming distance]] – The number of bits differing between two strings of binary digits
* [[Lee distance]]
* {{annotated link|Orthogonal convex hull}}
* [[Staircase paradox]] – The paradox that the limit of the lengths of finer and finer "staircase curves" does not tend to the length of the diagonal line segment the curves tend towards

{{clear}}

== External links ==

* [https://math.stackexchange.com/q/4365387/29780 Taxicab metric with stoplights]

==References==
{{reflist}}

== Further reading ==
* {{cite book |last=Gardner |first=Martin |author-link=Martin Gardner |year=1997 |title=The Last Recreations |publisher=Copernicus |chapter=10. Taxicab Geometry |pages=159–176 |isbn=0-387-94929-1 |chapter-url=https://archive.org/details/springer_10.1007-978-0-387-30389-5/page/n164/ }}
* {{cite book |last=Krause |first=Eugene F. |title=Taxicab Geometry |publisher=Addison-Wesley |year=1975 |isbn=0201039346 }} Reprinted by Dover (1986), {{isbn|0-486-25202-7}}.

==External links ==
* {{mathworld |title=Taxicab Metric |urlname=TaxicabMetric}}
* {{cite web |last=Malkevitch |first=Joe |date=October 1, 2007 |title=Taxi! |url=http://www.ams.org/publicoutreach/feature-column/fcarc-taxi |access-date=October 6, 2019 |work=American Mathematical Society}}


{{Lp spaces}}

[[Category:Digital geometry]]
[[Category:Distance]]
[[Category:Mathematical chess problems]]
[[Category:Metric geometry]]
[[Category:Norms (mathematics)]]