Taxicab geometry

Last updated February 29, 2024

Taxicab geometry or Manhattan geometry is geometry where the familiar Euclidean distance is ignored, and the distance between two points is instead defined to be the sum of the absolute differences of their respective Cartesian coordinates, a distance function (or 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 $L 1$ distance (see L^p space).^[1] This geometry has been used in regression analysis since the 18th century, and is often referred to as LASSO. Its geometric interpretation dates to non-Euclidean geometry of the 19th century and is due to Hermann Minkowski.

In the two-dimensional real coordinate space $\mathbb {R} ^{2},$ the taxicab distance between two points $(x_{1},y_{1})$ and $(x_{2},y_{2})$ is $\left|x_{1}-x_{2}\right|+\left|y_{1}-y_{2}\right|$ . That is, it is the sum of the absolute values of the differences in both coordinates.

Formal definition

The taxicab distance, $d_{\text{T}}$ , between two points $\mathbf {p} =(p_{1},p_{2},\dots ,p_{n}){\text{ and }}\mathbf {q} =(q_{1},q_{2},\dots ,q_{n})$ 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,

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|

For example, in $\mathbb {R} ^{2}$ , the taxicab distance between $\mathbf {p} =(p_{1},p_{2})$ and $\mathbf {q} =(q_{1},q_{2})$ is $\left|p_{1}-q_{1}\right|+\left|p_{2}-q_{2}\right|.$

History

The L¹ metric was used in regression analysis, as a measure of goodness of fit, in 1757 by Roger Joseph Boscovich.^[2] 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 L^p spaces, which include taxicab geometry as a special case, is credited to Riesz.^[3] In developing the geometry of numbers, Hermann Minkowski established his Minkowski inequality, stating that these spaces define normed vector spaces.^[4]

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 in Chicago.^[5]

Properties

Thought of as an additional structure layered on Euclidean space, taxicab distance depends on the orientation of the coordinate system and is changed by Euclidean rotation of the space, but is unaffected by translation or axis-aligned reflections. 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 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 congruent triangles.

Spheres

Grid points on a circle in taxicab geometry as the grid is made finer TaxicabGeometryCircle.svg — Grid points on a circle in taxicab geometry as the grid is made finer

In any metric space, a sphere is a set of points at a fixed distance, the radius , from a specific 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 an regular octahedron, whose points $\mathbf {p}$ satisfy the equation:

d_{\text{T}}(\mathbf {p} ,\mathbf {c} )=\sum _{i=1}^{n}|p_{i}-c_{i}|=r,

where $\mathbf {c}$ is the center and r is the radius. Points $\mathbf {p}$ on the unit sphere, a sphere of radius 1 centered at the origin, satisfy the equation ${\textstyle d_{\text{T}}(\mathbf {p} ,\mathbf {0} )=\sum _{i=1}^{n}|p_{i}|=1.}$

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 2r, so the circumference is 8r. Thus, in taxicab geometry, the value of the analog of the circle constant π, the ratio of circumference to diameter, is equal to 4.

A closed ball (or closed 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 is the von Neumann neighborhood of range r of its center.

A circle of radius r for the Chebyshev distance (L_∞ metric) on a plane is also a square with side length 2r 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₁ and L_∞ 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 $y=f(x)$ be a continuously differentiable function. Let $s$ be the taxicab arc length of the graph of $f$ on some interval $[a,b]$ . Take a partition of the interval into equal infinitesimal subintervals, and let $\Delta s_{i}$ be the taxicab length of the $i^{\text{th}}$ subarc. Then^[6]

\Delta s_{i}=\Delta x_{i}+\Delta y_{i}=\Delta x_{i}+|f(x_{i})-f(x_{i-1})|.

By the mean value theorem, there exists some point $x_{i}^{*}$ between $x_{i}$ and $x_{i-1}$ such that $f(x_{i})-f(x_{i-1})=f'(x_{i}^{*})dx_{i}$ .^[7] Then the previous equation can be written

\Delta s_{i}=\Delta x_{i}+|f'(x_{i}^{*})|\Delta x_{i}=\Delta x_{i}(1+|f'(x_{i}^{*})|).

Then $s$ is given as the sum of every partition of $s$ on $[a,b]$ as they get arbitrarily small.

${\begin{aligned}s&=\lim _{n\rightarrow \infty }\sum _{i=1}^{n}\Delta x_{i}(1+|f'(x_{i}^{*})|)\\&=\int _{a}^{b}1+|f'(x)|\,dx\end{aligned}}$

To test this, take the taxicab circle of radius $r$ centered at the origin. Its curve in the first quadrant is given by $f(x)=-x+r$ whose length is

s=\int _{0}^{r}1+|-1|dx=2r

Multiplying this value by $4$ to account for the remaining quadrants gives $8r$ , which agrees with the circumference of a taxicab circle.^[8] Now take the Euclidean circle of radius $r$ centered at the origin, which is given by $f(x)={\sqrt {r^{2}-x^{2}}}$ . Its arc length in the first quadrant is given by

{\begin{aligned}s&=\int _{0}^{r}1+|{\frac {-x}{\sqrt {r^{2}-x^{2}}}}|dx\\&=x+{\sqrt {r^{2}-x^{2}}}{\bigg |}_{0}^{r}\\&=r-(-r)\\&=2r\end{aligned}}

Accounting for the remaining quadrants gives $4\times 2r=8r$ again. Therefore, the circumference of the taxicab circle and the Euclidean circle in the taxicab metric are equal.^[9] In fact, for any function $f$ that is monotonic and differentiable with a continuous derivative over an interval $[a,b]$ , the arc length of $f$ over $[a,b]$ is $(b-a)+\mid f(b)-f(a)\mid$ .^[10]

Triangle congruence

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. Congruencetriangletaxicab.png — 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 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.^[11]

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 hypotenuses 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.^[12] 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 term for the parameter vector is expressed in terms of the $\ell _{1}$ norm (taxicab geometry) of the vector.^[13] 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.^[14]

Related Research Articles

Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's Elements, it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean spaces of any positive integer dimension n, which are called Euclidean n-spaces when one wants to specify their dimension. For n equal to one or two, they are commonly called respectively Euclidean lines and Euclidean planes. The qualifier "Euclidean" is used to distinguish Euclidean spaces from other spaces that were later considered in physics and modern mathematics.

In mathematics, a metric space is a set together with a notion of distance between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setting for studying many of the concepts of mathematical analysis and geometry.

<span class="mw-page-title-main">Tetrahedron</span> Polyhedron with 4 faces

In geometry, a tetrahedron, also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertices. The tetrahedron is the simplest of all the ordinary convex polyhedra.

In Euclidean geometry, an affine transformation or affinity is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles.

<span class="mw-page-title-main">Similarity (geometry)</span> Property of objects which are scaled or mirrored versions of each other

In Euclidean geometry, two objects are similar if they have the same shape, or if one has the same shape as the mirror image of the other. More precisely, one can be obtained from the other by uniformly scaling, possibly with additional translation, rotation and reflection. This means that either object can be rescaled, repositioned, and reflected, so as to coincide precisely with the other object. If two objects are similar, each is congruent to the result of a particular uniform scaling of the other.

In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols $, (where is the nabla operator), or . In a Cartesian coordinate system, the Laplacian is given by the sum of second partial derivatives of the function with respect to each independent variable. In other coordinate systems, such as cylindrical and spherical coordinates, the Laplacian also has a useful form. Informally, the Laplacian Δ f (p) of a function f at a point p measures by how much the average value of f over small spheres or balls centered at p deviates from f (p) .$

Elliptic geometry is an example of a geometry in which Euclid's parallel postulate does not hold. Instead, as in spherical geometry, there are no parallel lines since any two lines must intersect. However, unlike in spherical geometry, two lines are usually assumed to intersect at a single point. Because of this, the elliptic geometry described in this article is sometimes referred to as single elliptic geometry whereas spherical geometry is sometimes referred to as double elliptic geometry.

In mathematics, an isometry is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος isos meaning "equal", and μέτρον metron meaning "measure". If the transformation is from a metric space to itself, it is a kind of geometric transformation known as a motion.

In mathematics, conformal geometry is the study of the set of angle-preserving (conformal) transformations on a space.

In mathematics, a norm is a function from a real or complex vector space to the non-negative real numbers that behaves in certain ways like the distance from the origin: it commutes with scaling, obeys a form of the triangle inequality, and is zero only at the origin. In particular, the Euclidean distance in a Euclidean space is defined by a norm on the associated Euclidean vector space, called the Euclidean norm, the 2-norm, or, sometimes, the magnitude of the vector. This norm can be defined as the square root of the inner product of a vector with itself.

In mathematics, a hyperbolic metric space is a metric space satisfying certain metric relations between points. The definition, introduced by Mikhael Gromov, generalizes the metric properties of classical hyperbolic geometry and of trees. Hyperbolicity is a large-scale property, and is very useful to the study of certain infinite groups called Gromov-hyperbolic groups.

Screw theory is the algebraic calculation of pairs of vectors, such as angular and linear velocity, or forces and moments, that arise in the kinematics and dynamics of rigid bodies.

In geometry, a position or position vector, also known as location vector or radius vector, is a Euclidean vector that represents a point P in space. Its length represents the distance in relation to an arbitrary reference origin O, and its direction represents the angular orientation with respect to given reference axes. Usually denoted x, r, or s, it corresponds to the straight line segment from O to P. In other words, it is the displacement or translation that maps the origin to P:

<span class="mw-page-title-main">Geometry processing</span>

Geometry processing is an area of research that uses concepts from applied mathematics, computer science and engineering to design efficient algorithms for the acquisition, reconstruction, analysis, manipulation, simulation and transmission of complex 3D models. As the name implies, many of the concepts, data structures, and algorithms are directly analogous to signal processing and image processing. For example, where image smoothing might convolve an intensity signal with a blur kernel formed using the Laplace operator, geometric smoothing might be achieved by convolving a surface geometry with a blur kernel formed using the Laplace-Beltrami operator.

In Euclidean geometry, the Fermat point of a triangle, also called the Torricelli point or Fermat–Torricelli point, is a point such that the sum of the three distances from each of the three vertices of the triangle to the point is the smallest possible or, equivalently, the geometric median of the three vertices. It is so named because this problem was first raised by Fermat in a private letter to Evangelista Torricelli, who solved it.

In geometry, a three-dimensional space is a mathematical space in which three values (coordinates) are required to determine the position of a point. Most commonly, it is the three-dimensional Euclidean space, that is, the Euclidean space of dimension three, which models physical space. More general three-dimensional spaces are called 3-manifolds. The term may also refer colloquially to a subset of space, a three-dimensional region, a solid figure.

In mathematics, a $space, where is a real number, is a specific type of metric space. Intuitively, triangles in a space are "slimmer" than corresponding "model triangles" in a standard space of constant curvature . In a space, the curvature is bounded from above by . A notable special case is; complete spaces are known as "Hadamard spaces" after the French mathematician Jacques Hadamard.$

<span class="mw-page-title-main">Euclidean plane</span> Geometric model of the planar projection of the physical universe

In mathematics, a Euclidean plane is a Euclidean space of dimension two, denoted $or . It is a geometric space in which two real numbers are required to determine the position of each point. It is an affine space, which includes in particular the concept of parallel lines. It has also metrical properties induced by a distance, which allows to define circles, and angle measurement.$

<span class="mw-page-title-main">Pythagorean theorem</span> Relation between sides of a right triangle

In mathematics, the Pythagorean theorem or Pythagoras' theorem is a fundamental relation in Euclidean geometry between the three sides of a right triangle. It states that the area of the square whose side is the hypotenuse is equal to the sum of the areas of the squares on the other two sides.

In geometry, the Poincaré disk model, also called the conformal disk model, is a model of 2-dimensional hyperbolic geometry in which all points are inside the unit disk, and straight lines are either circular arcs contained within the disk that are orthogonal to the unit circle or diameters of the unit circle.

References

↑ Black, Paul E. "Manhattan distance". Dictionary of Algorithms and Data Structures. Retrieved October 6, 2019.
↑ Stigler, Stephen M. (1986). The History of Statistics: The Measurement of Uncertainty before 1900 . Harvard University Press. ISBN 9780674403406 . Retrieved October 6, 2019.
↑ Riesz, Frigyes (1910). "Untersuchungen über Systeme integrierbarer Funktionen". Mathematische Annalen (in German). 69 (4): 449–497. doi:10.1007/BF01457637. hdl: 10338.dmlcz/128558 . S2CID 120242933.
↑ Minkowski, Hermann (1910). Geometrie der Zahlen (in German). Leipzig and Berlin: R. G. Teubner. JFM 41.0239.03. MR 0249269 . Retrieved October 6, 2019.
↑ Menger, Karl (1952). You Will Like Geometry. A Guide Book for the Illinois Institute of Technology Geometry Exhibition. Chicago: Museum of Science and Industry.
Golland, Louise (1990). "Karl Menger and Taxicab Geometry". Mathematics Magazine. 63 (5): 326–327. doi:10.1080/0025570x.1990.11977548.
↑ Heinbockel, J.H. (2012). Introduction to Calculus Volume II. Old Dominion University. pp. 54–55.
↑ Penot, J.P. (1988-01-01). "On the mean value theorem". Optimization. 19 (2): 147–156. doi:10.1080/02331938808843330. ISSN 0233-1934.
↑ Petrović, Maja; Malešević, Branko; Banjac, Bojan; Obradović, Ratko (2014). Geometry of some taxicab curves. 4th International Scientific Conference on Geometry and Graphics. Serbian Society for Geometry and Graphics, University of Niš, Srbija. arXiv: 1405.7579 .
↑ Kemp, Aubrey (2018). Generalizing and Transferring Mathematical Definitions from Euclidean to Taxicab Geometry (PhD thesis). Georgia State University. doi: 10.57709/12521263 .
↑ Thompson, Kevin P. (2011). "The Nature of Length, Area, and Volume in Taxicab Geometry". International Electronic Journal of Geometry. 4 (2): 193–207. arXiv: 1101.2922 .
↑ Mironychev, Alexander (2018). "SAS and SSA Conditions for Congruent Triangles". Journal of Mathematics and System Science. 8 (2): 59–66.
↑ THOMPSON, KEVIN; DRAY, TEVIAN (2000). "Taxicab Angles and Trigonometry". Pi Mu Epsilon Journal. 11 (2): 87–96. ISSN 0031-952X. JSTOR 24340535.
↑ Donoho, David L. (March 23, 2006). "For most large underdetermined systems of linear equations the minimal $\ell _{1}$ -norm solution is also the sparsest solution". Communications on Pure and Applied Mathematics. 59 (6): 797–829. doi:10.1002/cpa.20132. S2CID 8510060.
↑ Lim, Kian Huat; Ferraris, Luciana; Filloux, Madeleine E.; Raphael, Benjamin J.; Fairbrother, William G. (July 5, 2011). "Using positional distribution to identify splicing elements and predict pre-mRNA processing defects in human genes". Proceedings of the National Academy of Sciences of the United States of America. 108 (27): 11093–11098. Bibcode:2011PNAS..10811093H. doi: 10.1073/pnas.1101135108 . PMC 3131313 . PMID 21685335.

External links

Weisstein, Eric W. "Taxicab Metric". MathWorld .
Malkevitch, Joe (October 1, 2007). "Taxi!". American Mathematical Society. Retrieved October 6, 2019.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Black, Paul E. "Manhattan distance". Dictionary of Algorithms and Data Structures. Retrieved October 6, 2019.

[Stigler19862-2] Stigler, Stephen M. (1986). The History of Statistics: The Measurement of Uncertainty before 1900 . Harvard University Press. ISBN 9780674403406 . Retrieved October 6, 2019.

[3] Riesz, Frigyes (1910). "Untersuchungen über Systeme integrierbarer Funktionen". Mathematische Annalen (in German). 69 (4): 449–497. doi:10.1007/BF01457637. hdl: 10338.dmlcz/128558 . S2CID 120242933.

[4] Minkowski, Hermann (1910). Geometrie der Zahlen (in German). Leipzig and Berlin: R. G. Teubner. JFM 41.0239.03. MR 0249269 . Retrieved October 6, 2019.

[5] Menger, Karl (1952). You Will Like Geometry. A Guide Book for the Illinois Institute of Technology Geometry Exhibition. Chicago: Museum of Science and Industry.
Golland, Louise (1990). "Karl Menger and Taxicab Geometry". Mathematics Magazine. 63 (5): 326–327. doi:10.1080/0025570x.1990.11977548.

[6] Heinbockel, J.H. (2012). Introduction to Calculus Volume II. Old Dominion University. pp. 54–55.

[7] Penot, J.P. (1988-01-01). "On the mean value theorem". Optimization. 19 (2): 147–156. doi:10.1080/02331938808843330. ISSN 0233-1934.

[8] Petrović, Maja; Malešević, Branko; Banjac, Bojan; Obradović, Ratko (2014). Geometry of some taxicab curves. 4th International Scientific Conference on Geometry and Graphics. Serbian Society for Geometry and Graphics, University of Niš, Srbija. arXiv: 1405.7579 .

[9] Kemp, Aubrey (2018). Generalizing and Transferring Mathematical Definitions from Euclidean to Taxicab Geometry (PhD thesis). Georgia State University. doi: 10.57709/12521263 .

[10] Thompson, Kevin P. (2011). "The Nature of Length, Area, and Volume in Taxicab Geometry". International Electronic Journal of Geometry. 4 (2): 193–207. arXiv: 1101.2922 .

[11] Mironychev, Alexander (2018). "SAS and SSA Conditions for Congruent Triangles". Journal of Mathematics and System Science. 8 (2): 59–66.

[12] THOMPSON, KEVIN; DRAY, TEVIAN (2000). "Taxicab Angles and Trigonometry". Pi Mu Epsilon Journal. 11 (2): 87–96. ISSN 0031-952X. JSTOR 24340535.

[13] Donoho, David L. (March 23, 2006). "For most large underdetermined systems of linear equations the minimal $\ell _{1}$ -norm solution is also the sparsest solution". Communications on Pure and Applied Mathematics. 59 (6): 797–829. doi:10.1002/cpa.20132. S2CID 8510060.

[lim2-14] Lim, Kian Huat; Ferraris, Luciana; Filloux, Madeleine E.; Raphael, Benjamin J.; Fairbrother, William G. (July 5, 2011). "Using positional distribution to identify splicing elements and predict pre-mRNA processing defects in human genes". Proceedings of the National Academy of Sciences of the United States of America. 108 (27): 11093–11098. Bibcode:2011PNAS..10811093H. doi: 10.1073/pnas.1101135108 . PMC 3131313 . PMID 21685335.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]