Taxicab geometry
Taxicab geometry or Manhattan geometry is
The taxicab distance is also sometimes known as rectilinear distance or L1 distance (see Lp 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 the taxicab distance between two points and is . That is, it is the sum of the absolute values of the differences in both coordinates.
Formal definition
The taxicab distance, , between two points in an n-dimensional
History
The L1 metric was used in
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
In any
where is the center and r is the radius. Points on the unit sphere, a sphere of radius 1 centered at the origin, satisfy the equation
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
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 L1 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 be a continuously differentiable function. Let be the taxicab arc length of the graph of on some interval . Take a partition of the interval into equal infinitesimal subintervals, and let be the taxicab length of the subarc. Then[6]
By the mean value theorem, there exists some point between and such that .[7] Then the previous equation can be written
Then is given as the sum of every partition of on as they get arbitrarily small.
To test this, take the taxicab circle of radius centered at the origin. Its curve in the first quadrant is given by whose length is
Multiplying this value by to account for the remaining quadrants gives , which agrees with the circumference of a taxicab circle.[8] Now take the Euclidean circle of radius centered at the origin, which is given by . Its arc length in the first quadrant is given by
Accounting for the remaining quadrants gives again. Therefore, the circumference of the taxicab circle and the Euclidean circle in the taxicab metric are equal.[9] In fact, for any function that is monotonic and differentiable with a continuous derivative over an interval , the arc length of over is .[10]
Triangle congruence
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 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
See also
- Chebyshev distance
- Hamming distance – The number of bits differing between two strings of binary digits
- Lee distance
- Orthogonal convex hull – Minimal superset that intersects each axis-parallel line in an interval
- 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
References
- ^ Black, Paul E. "Manhattan distance". Dictionary of Algorithms and Data Structures. Retrieved October 6, 2019.
- ISBN 9780674403406. Retrieved October 6, 2019.
- S2CID 120242933.
- MR 0249269. Retrieved October 6, 2019.
- .
- ^ Heinbockel, J.H. (2012). Introduction to Calculus Volume II. Old Dominion University. pp. 54–55.
- ISSN 0233-1934.
- arXiv:1405.7579.
- .
- arXiv:1101.2922.
- ^ Mironychev, Alexander (2018). "SAS and SSA Conditions for Congruent Triangles". Journal of Mathematics and System Science. 8 (2): 59–66.
- JSTOR 24340535.
- ^ Donoho, David L. (March 23, 2006). "For most large underdetermined systems of linear equations the minimal -norm solution is also the sparsest solution". Communications on Pure and Applied Mathematics. 59 (6): 797–829. S2CID 8510060.
- PMID 21685335.
Further reading
- ISBN 0-387-94929-1.
- Krause, Eugene F. (1975). Taxicab Geometry. Addison-Wesley. ISBN 0-486-25202-7.
External links
- Weisstein, Eric W. "Taxicab Metric". MathWorld.
- Malkevitch, Joe (October 1, 2007). "Taxi!". American Mathematical Society. Retrieved October 6, 2019.