![Manhattan distance](https://upload.wikimedia.org/wikipedia/commons/0/08/Manhattan_distance.svg)
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 c ...
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 mathematics, Greek mathematician Euclid, which he described in his textbook on geometry: the ''Euclid's Elements, Elements''. Euclid's approach consists in assuming a small ...
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 a ...
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
norm (see
''Lp'' space),
snake
Snakes are elongated, Limbless vertebrate, limbless, carnivore, carnivorous reptiles of the suborder Serpentes . Like all other Squamata, squamates, snakes are ectothermic, amniote vertebrates covered in overlapping Scale (zoology), scales. Ma ...
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 original counties of the U.S. state ...
, 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 geo ...
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 t ...
.
In
, 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 vectors
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 can ...
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 in t ...
, 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 ...
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 t ...
. More formally,
For example, in
, the taxicab distance between
and
is
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 geo ...
, 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 t ...
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 Reflection or reflexion may refer to:
Science and technology
* Reflection (physics), a common wave phenomenon
** Specular reflection, reflection from a smooth surface
*** Mirror image, a reflection in a mirror or in water
** Signal reflection, in ...
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 mathematics, Greek mathematician Euclid, which he described in his textbook on geometry: the ''Euclid's Elements, Elements''. Euclid's approach consists in assuming a small ...
) 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
Congruence may refer to:
Mathematics
* Congruence (geometry), being the same size and shape
* Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure
* In mod ...
unless the mentioned sides are parallel.
Balls
![TaxicabGeometryCircle](https://upload.wikimedia.org/wikipedia/commons/d/de/TaxicabGeometryCircle.svg)
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 adj ...
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
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 oc ...
, 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
is 4 in this geometry. The formula for the unit circle in taxicab geometry is
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 t ...
and
in
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 the or ...
.
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 na ...
(
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 L
1 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
be a
continuously 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 its ...
function in
. Let
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 (geometry), line, but that does not have to be Linearity, straight.
Intuitively, a curve may be thought of as the trace left by a moving point (ge ...
defined by
on some interval
. Then the taxicab length of the
infinitesimal
regular partition of the arc,
, is given by:
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 i ...
, there exists some point
between
and
such that
.
Then
is given as the sum of every partition of
on