Taxicab geometry

Circles in discrete and continuous taxicab geometry

A topological ball is a set of points with a fixed distance, called the radius, from a point called the center. In n-dimensional Euclidean geometry, the balls are spheres. 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 two dimensions, these are squares 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 ${\displaystyle {\sqrt {2}}r}$ 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 ${\displaystyle \pi }$ is 4 in this geometry. The formula for the unit circle in taxicab geometry is ${\displaystyle |x|+|y|=1}$ in Cartesian coordinates and

$${\displaystyle r={\frac {1}{\left|\sin \theta \right|+\left|\cos \theta \right|}}}$$

in polar coordinates.

A circle of radius 1 (using this distance) is the von Neumann neighborhood 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.

Let ${\displaystyle y=f(x)}$ be a continuously differentiable function in ${\displaystyle \mathbb {R} ^{2}}$. Let ${\displaystyle s}$ be the taxicab arc length of the planar curve defined by ${\displaystyle f}$ on some interval ${\displaystyle [a,b]}$. Then the taxicab length of the ${\displaystyle i^{\text{th}}}$ infinitesimal regular partition of the arc, ${\displaystyle \Delta s_{i}}$, is given by:[2]

${\displaystyle \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 ${\displaystyle x_{i}^{*}}$ between ${\displaystyle x_{i}}$ and ${\displaystyle x_{i-1}}$such that ${\displaystyle f(x_{i})-f(x_{i-1})=f'(x_{i}^{*})dx_{i}}$.[3]

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

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

${\displaystyle {\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}}}$

Curves defined by monotone increasing or decreasing functions have the same taxicab arc length as long as they share the same endpoints.

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

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

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

${\displaystyle {\begin{aligned}s&=\int _{0}^{r}1+|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 ${\displaystyle 4\times 2r=8r}$ again. Therefore, the circumference of the taxicab circle and the Euclidean circle in the taxicab metric are equal.[5] In fact, for any function ${\displaystyle f}$ that is monotonic and differentiable with a continuous derivative over an interval ${\displaystyle [a,b]}$, the arc length of ${\displaystyle f}$ over ${\displaystyle [a,b]}$ is ${\displaystyle (b-a)+\mid f(b)-f(a)\mid }$.[6]

In solving an underdetermined system of linear equations, the regularization term for the parameter vector is expressed in terms of the ${\displaystyle \ell _{1}}$-norm (taxicab geometry) of the vector.[7] This approach appears in the signal recovery framework called compressed sensing.

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.[8]