HOME

TheInfoList



OR:

A taxicab geometry or a Manhattan geometry is a
geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is ...
whose usual distance function or
metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathema ...
of
Euclidean geometry Euclidean geometry is a mathematical system attributed to ancient Greek mathematician Euclid, which he described in his textbook on geometry: the ''Elements''. Euclid's approach consists in assuming a small set of intuitively appealing axioms ...
is replaced by a new metric in which the
distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
between two points is the sum of the
absolute difference The absolute difference of two real numbers x and y is given by , x-y, , the absolute value of their difference. It describes the distance on the real line between the points corresponding to x and y. It is a special case of the Lp distance for ...
s of their
Cartesian coordinate A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in ...
s. The taxicab metric is also known as rectilinear distance, ''L''1 distance, ''L''1 distance or \ell_1 norm (see ''Lp'' space),
snake Snakes are elongated, limbless, carnivorous reptiles of the suborder Serpentes . Like all other squamates, snakes are ectothermic, amniote vertebrates covered in overlapping scales. Many species of snakes have skulls with several more joints ...
distance, city block distance, Manhattan distance or Manhattan length. The latter names refer to the rectilinear street layout on the island of
Manhattan Manhattan (), known regionally as the City, is the most densely populated and geographically smallest of the five boroughs of New York City. The borough is also coextensive with New York County, one of the List of counties in New York, origin ...
, where the shortest path a taxi travels between two points is the sum of the absolute values of distances that it travels on avenues and on streets. The geometry has been used in
regression analysis In statistical modeling, regression analysis is a set of statistical processes for estimating the relationships between a dependent variable (often called the 'outcome' or 'response' variable, or a 'label' in machine learning parlance) and one ...
since the 18th century, and is often referred to as
LASSO A lasso ( or ), also called lariat, riata, or reata (all from Castilian, la reata 're-tied rope'), is a loop of rope designed as a restraint to be thrown around a target and tightened when pulled. It is a well-known tool of the Spanish an ...
. The geometric interpretation dates to
non-Euclidean geometry In mathematics, non-Euclidean geometry consists of two geometries based on axioms closely related to those that specify Euclidean geometry. As Euclidean geometry lies at the intersection of metric geometry and affine geometry, non-Euclidean ge ...
of the 19th century and is due to
Hermann Minkowski Hermann Minkowski (; ; 22 June 1864 – 12 January 1909) was a German mathematician and professor at Königsberg, Zürich and Göttingen. He created and developed the geometry of numbers and used geometrical methods to solve problems in number ...
. In \mathbb^2 , the taxicab distance between two points (x_1, y_1) and (x_2, y_2) is \left, x_1 - x_2\ + \left, y_1 - y_2\. That is, it is the sum of the absolute values of the differences in both coordinates.


Formal definition

The taxicab distance, d_\text, between two vectors \mathbf = (p_1, p_2, \dots, p_n) \text \mathbf = (q_1, q_2, \dots, q_n) in an ''n''-dimensional
real Real may refer to: Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish colonial real Music Albums * ''Real'' (L'Arc-en-Ciel album) (2000) * ''Real'' (Bright album) (2010) ...
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but ca ...
with fixed
Cartesian coordinate system A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured i ...
, is the sum of the lengths of the projections of the
line segment In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between i ...
between the points onto the
coordinate axes A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in ...
. More formally,d_\text(\mathbf, \mathbf) = \left\, \mathbf - \mathbf\right\, _\text = \sum_^n \left, p_i - q_i\For example, in \mathbb^2 , the taxicab distance between \mathbf = (p_1,p_2) and \mathbf = (q_1,q_2) is \left, p_1 - q_1 \ + \left, p_2 - q_2 \.


History

The ''L''1 metric was used in
regression analysis In statistical modeling, regression analysis is a set of statistical processes for estimating the relationships between a dependent variable (often called the 'outcome' or 'response' variable, or a 'label' in machine learning parlance) and one ...
in 1757 by
Roger Joseph Boscovich Roger Joseph Boscovich ( hr, Ruđer Josip Bošković; ; it, Ruggiero Giuseppe Boscovich; la, Rogerius (Iosephus) Boscovicius; sr, Руђер Јосип Бошковић; 18 May 1711 – 13 February 1787) was a physicist, astronomer, ...
. The geometric interpretation dates to the late 19th century and the development of
non-Euclidean geometries In mathematics, non-Euclidean geometry consists of two geometries based on axioms closely related to those that specify Euclidean geometry. As Euclidean geometry lies at the intersection of metric geometry and affine geometry, non-Euclidean g ...
, notably by
Hermann Minkowski Hermann Minkowski (; ; 22 June 1864 – 12 January 1909) was a German mathematician and professor at Königsberg, Zürich and Göttingen. He created and developed the geometry of numbers and used geometrical methods to solve problems in number ...
and his
Minkowski inequality In mathematical analysis, the Minkowski inequality establishes that the L''p'' spaces are normed vector spaces. Let ''S'' be a measure space, let and let ''f'' and ''g'' be elements of L''p''(''S''). Then is in L''p''(''S''), and we have the tr ...
, of which this geometry is a special case, particularly used in the
geometry of numbers Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice in \mathbb R^n, and the study of these lattices provides fundamental information ...
, . The formalization of ''L''p spaces is credited to .


Properties

Taxicab distance depends on the
rotation Rotation, or spin, is the circular movement of an object around a '' central axis''. A two-dimensional rotating object has only one possible central axis and can rotate in either a clockwise or counterclockwise direction. A three-dimensional ...
of the coordinate system, but does not depend on its reflection about a coordinate axis or its
translation Translation is the communication of the Meaning (linguistic), meaning of a #Source and target languages, source-language text by means of an Dynamic and formal equivalence, equivalent #Source and target languages, target-language text. The ...
. Taxicab geometry satisfies all of
Hilbert's axioms Hilbert's axioms are a set of 20 assumptions proposed by David Hilbert in 1899 in his book '' Grundlagen der Geometrie'' (tr. ''The Foundations of Geometry'') as the foundation for a modern treatment of Euclidean geometry. Other well-known modern ...
(a formalization of
Euclidean geometry Euclidean geometry is a mathematical system attributed to ancient Greek mathematician Euclid, which he described in his textbook on geometry: the ''Elements''. Euclid's approach consists in assuming a small set of intuitively appealing axioms ...
) except for the side-angle-side axiom, as two triangles with equally "long" two sides and an identical angle between them are typically not congruent unless the mentioned sides are parallel.


Balls

A topological ball is a set of points with a fixed distance, called the ''
radius In classical geometry, a radius ( : radii) of a circle or sphere is any of the line segments from its center to its perimeter, and in more modern usage, it is also their length. The name comes from the latin ''radius'', meaning ray but also the ...
'', from a point called the ''
center Center or centre may refer to: Mathematics *Center (geometry), the middle of an object * Center (algebra), used in various contexts ** Center (group theory) ** Center (ring theory) * Graph center, the set of all vertices of minimum eccentricity ...
''. In ''n''-dimensional Euclidean geometry, the balls are
spheres The Synchronized Position Hold Engage and Reorient Experimental Satellite (SPHERES) are a series of miniaturized satellites developed by MIT's Space Systems Laboratory for NASA and US Military, to be used as a low-risk, extensible test bed for the ...
. In taxicab geometry, distance is determined by a different metric than in Euclidean geometry, and the shape of the ball changes as well. In ''n'' dimensions, a taxicab ball is in the shape of an ''n''-dimensional
orthoplex In geometry, a cross-polytope, hyperoctahedron, orthoplex, or cocube is a regular, convex polytope that exists in ''n''- dimensional Euclidean space. A 2-dimensional cross-polytope is a square, a 3-dimensional cross-polytope is a regular octahed ...
. In two dimensions, these are
squares In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length ...
with sides oriented at a 45° angle to the coordinate axes. The image to the right shows why this is true, by showing in red the set of all points with a fixed distance from a center, shown in blue. As the size of the city blocks diminishes, the points become more numerous and become a rotated square in a continuous taxicab geometry. While each side would have length \sqrtr using a
Euclidean metric In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore o ...
, where ''r'' is the circle's radius, its length in taxicab geometry is 2''r''. Thus, a circle's circumference is 8''r''. Thus, the value of a geometric analog to \pi is 4 in this geometry. The formula for the unit circle in taxicab geometry is , x, + , y, = 1 in
Cartesian coordinates A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in ...
andr = \fracin
polar coordinates In mathematics, the polar coordinate system is a two-dimensional coordinate system in which each point on a plane is determined by a distance from a reference point and an angle from a reference direction. The reference point (analogous to th ...
. A circle of radius 1 (using this distance) is the
von Neumann neighborhood In cellular automata, the von Neumann neighborhood (or 4-neighborhood) is classically defined on a two-dimensional square lattice and is composed of a central cell and its four adjacent cells. The neighborhood is named after John von Neumann, ...
of its center. A circle of radius ''r'' for the
Chebyshev distance In mathematics, Chebyshev distance (or Tchebychev distance), maximum metric, or L∞ metric is a metric defined on a vector space where the distance between two vectors is the greatest of their differences along any coordinate dimension. It is n ...
( L 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 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 In metric geometry, an injective metric space, or equivalently a hyperconvex metric space, is a metric space with certain properties generalizing those of the real line and of L∞ distances in higher-dimensional vector spaces. These properties can ...
.


Arc Length

Let y = f(x) be a continuously differentiable function in \mathbb^2. Let s be the taxicab
arc length ARC may refer to: Business * Aircraft Radio Corporation, a major avionics manufacturer from the 1920s to the '50s * Airlines Reporting Corporation, an airline-owned company that provides ticket distribution, reporting, and settlement services * ...
of the planar
curve In mathematics, a curve (also called a curved line in older texts) is an object similar to a line, but that does not have to be straight. Intuitively, a curve may be thought of as the trace left by a moving point. This is the definition that ...
defined by f on some interval ,b. Then the taxicab length of the i^ infinitesimal regular partition of the arc, \Delta s_i, is given by: \Delta s_i = \Delta x_i + \Delta y_i = \Delta x_i+ , f(x_i) - f(x_), By the
Mean Value Theorem In mathematics, the mean value theorem (or Lagrange theorem) states, roughly, that for a given planar arc between two endpoints, there is at least one point at which the tangent to the arc is parallel to the secant through its endpoints. It ...
, there exists some point x^*_i between x_i and x_ such that f(x_i) - f(x_) = f'(x^*_i)dx_i. \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 ,b/math> as they get arbitrarily small.\begin s &= \lim_ \sum_^ \Delta x_i(1+, f'(x^*_i), ) \\ & = \int_^ 1+, f'(x), \,dx \end To test this, take the taxicab circle of
radius In classical geometry, a radius ( : radii) of a circle or sphere is any of the line segments from its center to its perimeter, and in more modern usage, it is also their length. The name comes from the latin ''radius'', meaning ray but also the ...
r centered at the origin. Its curve in the first quadrant is given by f(x)=-x+r whose length is s = \int_^ 1+, -1, dx = 2r Multiplying this value by 4 to account for the remaining quadrants gives 8r , which agrees with the
circumference In geometry, the circumference (from Latin ''circumferens'', meaning "carrying around") is the perimeter of a circle or ellipse. That is, the circumference would be the arc length of the circle, as if it were opened up and straightened out to ...
of a taxicab circle. Now take the Euclidean circle of radius r centered at the origin, which is given by f(x) = \sqrt . Its arc length in the first quadrant is given by \begin s &= \int_^ 1+, x\sqrt, dx\\ &= x+\sqrt \bigg, ^_\\ &= r-(-r)\\ &= 2r \end Accounting for the remaining quadrants gives 4 \times 2r = 8r again. Therefore, the
circumference In geometry, the circumference (from Latin ''circumferens'', meaning "carrying around") is the perimeter of a circle or ellipse. That is, the circumference would be the arc length of the circle, as if it were opened up and straightened out to ...
of the taxicab circle and the Euclidean circle in the taxicab
metric Metric or metrical may refer to: * Metric system, an internationally adopted decimal system of measurement * An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement Mathematics In mathema ...
are equal. In fact, for any function f that is monotonic and
differentiable In mathematics, a differentiable function of one real variable is a function whose derivative exists at each point in its domain. In other words, the graph of a differentiable function has a non-vertical tangent line at each interior point in it ...
with a continuous
derivative In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. ...
over an interval ,b/math>, the arc length of f over
, b The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
/math> is (b-a) + \mid f(b)-f(a) \mid.


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. Take, for example, two right isosceles taxicab triangles whose angles measure 45-90-45. The two legs of both triangles have taxilength 2, but the
hypotenuse In geometry, a hypotenuse is the longest side of a right-angled triangle, the side opposite the right angle. The length of the hypotenuse can be found using the Pythagorean theorem, which states that the square of the length of the hypotenuse equ ...
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. 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 In mathematics, a system of linear equations or a system of polynomial equations is considered underdetermined if there are fewer equations than unknowns (in contrast to an overdetermined system, where there are more equations than unknowns). The ...
of linear equations, the regularization term for the parameter vector is expressed in terms of the \ell_1 norm (taxicab geometry) of the vector. 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 RNA splicing is a process in molecular biology where a newly-made precursor messenger RNA (pre-mRNA) transcript is transformed into a mature messenger RNA (mRNA). It works by removing all the introns (non-coding regions of RNA) and ''splicing'' b ...
positional distributions of hexamers, which plot the probability of each hexamer appearing at each given
nucleotide Nucleotides are organic molecules consisting of a nucleoside and a phosphate. They serve as monomeric units of the nucleic acid polymers – deoxyribonucleic acid (DNA) and ribonucleic acid (RNA), both of which are essential biomolecules with ...
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.


See also

* * * * * * * * *


External links

* * * * *


References

{{Reflist Digital geometry Metric geometry Mathematical chess problems Norms (mathematics) Distance