Taxicab geometry, considered by
Hermann MinkowskiHermann Minkowski was a German mathematician of Ashkenazi Jewish descent, who created and developed the geometry of numbers and who used geometrical methods to solve difficult problems in number theory, mathematical physics, and the theory of relativity.- Life and work :Hermann Minkowski was born...
in the 19th century, is a form of
geometryGeometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
in which the usual distance function or
metricIn mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
of
Euclidean geometryEuclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...
is replaced by a new metric in which the
distanceDistance is a numerical description of how far apart objects are. In physics or everyday discussion, distance may refer to a physical length, or an estimation based on other criteria . In mathematics, a distance function or metric is a generalization of the concept of physical distance...
between two points is the sum of the
absolute differenceThe absolute difference of two real numbers x, 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...
s of their coordinates. The taxicab metric is also known as rectilinear distance, L
1 distance or
1 norm (see
Lp spaceIn mathematics, the Lp spaces are function spaces defined using a natural generalization of the p-norm for finite-dimensional vector spaces...
), city block distance, Manhattan distance, or Manhattan length, with corresponding variations in the name of the geometry. The latter names allude to the
grid layout of most streetsThe Commissioners' Plan of 1811 was the original design plan for the streets of Manhattan, which put in place the grid plan that has defined Manhattan to this day....
on the island of
ManhattanManhattan is the oldest and the most densely populated of the five boroughs of New York City. Located primarily on the island of Manhattan at the mouth of the Hudson River, the boundaries of the borough are identical to those of New York County, an original county of the state of New York...
, which causes the shortest path a car could take between two points in the
boroughA borough is an administrative division in various countries. In principle, the term borough designates a self-governing township although, in practice, official use of the term varies widely....
to have length equal to the points' distance in taxicab geometry.
Formal description
The taxicab distance,
, between two vectors
in an n-dimensional
realIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
vector spaceA vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
with fixed
Cartesian coordinate systemA Cartesian coordinate system specifies each point uniquely in a plane by a pair of numerical coordinates, which are the signed distances from the point to two fixed perpendicular directed lines, measured in the same unit of length...
, is the sum of the lengths of the projections of the
line segmentIn geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
between the points onto the coordinate axes. More formally,
where
are vectors.
For example, in the
planeIn mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...
, the taxicab distance between
and
is
Taxicab distance depends on the
rotationA rotation is a circular movement of an object around a center of rotation. A three-dimensional object rotates always around an imaginary line called a rotation axis. If the axis is within the body, and passes through its center of mass the body is said to rotate upon itself, or spin. A rotation...
of the coordinate system, but does not depend on its
reflectionIn mathematics, a reflection is a mapping from a Euclidean space to itself that is an isometry with a hyperplane as set of fixed points; this set is called the axis or plane of reflection. The image of a figure by a reflection is its mirror image in the axis or plane of reflection...
about a coordinate axis or its
translationIn Euclidean geometry, a translation moves every point a constant distance in a specified direction. A translation can be described as a rigid motion, other rigid motions include rotations and reflections. A translation can also be interpreted as the addition of a constant vector to every point, or...
. Taxicab geometry satisfies all of
Hilbert's axiomsHilbert's axioms are a set of 20 assumptions proposed by David Hilbert in 1899 in his book Grundlagen der Geometrie , as the foundation for a modern treatment of Euclidean geometry...
(a formalization of
Euclidean geometryEuclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...
) except for the
side-angle-side axiomIn geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...
, as one can generate two triangles each with two sides and the angle between them the same, and have them not be congruent.
A
circleA circle is a simple shape of Euclidean geometry consisting of those points in a plane that are a given distance from a given point, the centre. The distance between any of the points and the centre is called the radius....
is a set of points with a fixed distance, called the
radiusIn classical geometry, a radius of a circle or sphere is any line segment from its center to its perimeter. By extension, the radius of a circle or sphere is the length of any such segment, which is half the diameter. If the object does not have an obvious center, the term may refer to its...
, from a point called the center. In taxicab geometry, distance is determined by a different metric than in Euclidean geometry, and the shape of circles changes as well. Taxicab circles are
squareIn geometry, a square is a regular quadrilateral. This means that it has four equal sides and four equal angles...
s 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 √2r using a Euclidean metric, where r is the circle's radius, its length in taxicab geometry is 2r. Thus, a circle's circumference is 8r. Thus, the value of a geometric analog to
' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...
is 4 in this geometry. The formula for the unit circle in taxicab geometry is
in Cartesian coordinates and
in polar coordinates.
A circle of radius r for the
Chebyshev distanceIn mathematics, Chebyshev 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...
(
L∞ metricIn mathematics, the Lp spaces are function spaces defined using a natural generalization of the p-norm for finite-dimensional vector spaces...
) 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
1 and L
∞ metrics does not generalize to higher dimensions.
The use of Manhattan distance leads to a strange concept: when the resolution of the Taxicab geometry is made larger, approaching infinity (the size of division of the axis approaches 0), it seems intuitive that the Manhattan distance would approach the Euclidean metric
but it does not. This is essentially a consequence of being forced to adhere to single-axis movement: when following the Manhattan metric, one cannot move diagonally (in more than one axis simultaneously).
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 spaceIn 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...
.
A circle of radius 1 (using this distance) is the
von Neumann neighborhoodIn cellular automata, the von Neumann neighborhood comprises the four cells orthogonally surrounding a central cell on a two-dimensional square lattice. The neighborhood is named after John von Neumann, who used it for his pioneering cellular automata including the Universal Constructor...
of its center.
Measures of distances in chess
In
chessChess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
, the distance between squares on the
chessboardA chessboard is the type of checkerboard used in the board game chess, and consists of 64 squares arranged in two alternating colors...
for
rookA rook is a piece in the strategy board game of chess. Formerly the piece was called the castle, tower, marquess, rector, and comes...
s is measured in Manhattan distance;
kingIn chess, the king is the most important piece. The object of the game is to trap the opponent's king so that its escape is not possible . If a player's king is threatened with capture, it is said to be in check, and the player must remove the threat of capture on the next move. If this cannot be...
s and
queenThe queen is the most powerful piece in the game of chess, able to move any number of squares vertically, horizontally, or diagonally. Each player starts the game with one queen, placed in the middle of the first rank next to the king. With the chessboard oriented correctly, the white queen starts...
s use
Chebyshev distanceIn mathematics, Chebyshev 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...
, and
bishopA bishop is a piece in the board game of chess. Each player begins the game with two bishops. One starts between the king's knight and the king, the other between the queen's knight and the queen...
s use the Manhattan distance (between squares of the same color) on the chessboard rotated 45 degrees, i.e., with its diagonals as coordinate axes. To reach from one square to another, only kings require the number of moves equal to the distance; rooks, queens and bishops require one or two moves (on an empty board, and assuming that the move is possible at all in the bishop's case).
See also
- Normed vector space
In mathematics, with 2- or 3-dimensional vectors with real-valued entries, the idea of the "length" of a vector is intuitive and can easily be extended to any real vector space Rn. The following properties of "vector length" are crucial....
- Metric
In mathematics, a metric or distance function is a function which defines a distance between elements of a set. A set with a metric is called a metric space. A metric induces a topology on a set but not all topologies can be generated by a metric...
- Orthogonal convex hull
In Euclidean geometry, a set K\subset\R^n is defined to be orthogonally convex if, for every line L that is parallel to one of the axes of the Cartesian coordinate system, the intersection of K with L is empty, a point, or a single interval...
- Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
- Fifteen puzzle
- Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...
- Manhattan wiring
Manhattan wiring is a technique for laying out circuits in computer engineering. Inputs to a circuit are aligned into a grid, and the circuit "taps" them perpendicularly...
- Réti endgame study
The Réti endgame study is a chess endgame study by Richard Réti. It was published in 1921 in Kagans Neueste Schachnachrichten. It demonstrates how a king can make multiple threats and how it can take more than one path to a given location, using the same number of moves...
External links
- city-block metric on PlanetMath
PlanetMath is a free, collaborative, online mathematics encyclopedia. The emphasis is on rigour, openness, pedagogy, real-time content, interlinked content, and also community of about 24,000 people with various maths interests. Intended to be comprehensive, the project is hosted by the Digital...
- Manhattan distance. Paul E. Black, Dictionary of Algorithms and Data Structures, NIST
- Taxi! - AMS column about Taxicab geometry