Distance

Euclidean Distance

Two-Dimensional Space

Definition

Euclidean distance, also commonly called Euclidean distance, is defined as follows. In a Cartesian coordinate system, let points $A,B$ have coordinates $A(x_1,y_1),B(x_2,y_2)$ respectively. Then the Euclidean distance between them is:

Explanation

For example, suppose that in a Cartesian coordinate system there are two points $A(6,5),B(2,2)$. Using the formula, we can easily obtain the Euclidean distance between $A,B$:

In addition, the Euclidean distance from $P(x,y)$ to the origin can be written as:

n-Dimensional Space

Introduction

What is the Euclidean-distance formula for two points in three-dimensional space? Let us examine the figure below.

It is easy to see that in $\triangle ADC$, $\angle ADC = 90^\circ$; in $\triangle ACB$, $\angle ACB = 90^\circ$.

Definition

It follows that the Euclidean-distance formula in three-dimensional space is:

Explanation

NOIP2017 Advanced Group Cheese uses this fact and can serve as an example problem for Euclidean distance.

Continuing in this way, we obtain the Euclidean-distance formula in $n$-dimensional space: for $\vec A(x_{11}, x_{12}, \cdots,x_{1n}) ,~ \vec B(x_{21}, x_{22}, \cdots,x_{2n})$, we have

Although Euclidean distance is very useful, it also has an obvious drawback. When computing the distance between two lattice points, the answer is often a floating-point number and therefore has some error.

Manhattan Distance

Definition

In two-dimensional space, Manhattan distance is the sum of the absolute differences of the x- and y-coordinates of two points. Given points $A(x_1,y_1),B(x_2,y_2)$, the Manhattan distance between $A,B$ is:

Explanation

Observe the figure below:

Between $A,B$, the yellow and orange lines represent Manhattan distance, the red and blue lines represent equivalent Manhattan distances, and the green line represents Euclidean distance.

In the same example, the coordinates of $A,B$ in the figure below are $A(25,20),B(10,10)$.

Using the formula, we can easily obtain the Manhattan distance between $A,B$:

By derivation, we obtain the formula for Manhattan distance in $n$-dimensional space:

Properties

In addition to its formula, Manhattan distance has the following mathematical properties:

• Non-negativity: Manhattan distance is non-negative, that is, $d(i,j)\geq 0$.
• Identity: the Manhattan distance from a point to itself is $0$, that is, $d(i,i) = 0$.
• Symmetry: the Manhattan distance from $A$ to $B$ equals that from $B$ to $A$, that is, $d(i,j) = d(j,i)$.
• Triangle inequality: the direct distance from point $i$ to $j$ is no greater than the distance through any other point $k$, that is, $d(i,j)\leq d(i,k)+d(k,j)$.

Example

P5098「USACO04OPEN」Cave Cows 3

From the statement, for the expression $|x_1-x_2|+|y_1-y_2|$, we may assume $x_1 - x_2 \geq 0$ and split into two cases according to the sign of $y_1 - y_2$:

• $(y_1 - y_2 \geq 0)\rightarrow |x_1-x_2|+|y_1-y_2|=x_1 + y_1 - (x_2 + y_2)$

• $(y_1 - y_2 < 0)\rightarrow |x_1-x_2|+|y_1-y_2|=x_1 - y_1 - (x_2 - y_2)$

The answer can be obtained by finding the maximum and minimum values of $x+y, x-y$.

#include <algorithm>
#include <cstdio>
using namespace std;

int main() {
  int n, x, y, minx = 0x7fffffff, maxx = 0, miny = 0x7fffffff, maxy = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &x, &y);
    minx = min(minx, x + y), maxx = max(maxx, x + y);
    miny = min(miny, x - y), maxy = max(maxy, x - y);
  }
  printf("%d\n", max(maxx - minx, maxy - miny));
  return 0;
}

minx = 0x7FFFFFFF
maxx = 0
miny = 0x7FFFFFFF
maxy = 0
n = int(input())
for i in range(1, n + 1):
    x, y = map(lambda x: int(x), input().split())
    minx = min(minx, x + y)
    maxx = max(maxx, x + y)
    miny = min(miny, x - y)
    maxy = max(maxy, x - y)
print(max(maxx - minx, maxy - miny))

There is also a second method: transform Manhattan distance into Chebyshev distance, as discussed later.

Chebyshev Distance

Definition

Chebyshev distance is a metric on a vector space in which the distance between two points is defined as the maximum absolute difference among their coordinates.¹

In two-dimensional space, the Chebyshev distance between two points is the maximum of the absolute differences of their x- and y-coordinates. Given points $A(x_1,y_1),B(x_2,y_2)$, the Chebyshev distance between $A,B$ is:

The Chebyshev-distance formula in $n$-dimensional space is:

Explanation

Again using the same example, the coordinates of $A,B$ in the figure below are $A(25,20),B(10,10)$.

Converting Between Manhattan and Chebyshev Distance

Procedure

First, consider plotting all points in the Cartesian coordinate system whose Manhattan distance from the origin is $1$.

The formula gives the equation $|x| + |y| = 1$.

Expanding the absolute values gives $4$ linear functions:

Plotting these $4$ functions in the Cartesian coordinate system gives a square with side length $\sqrt{2}$, as shown below:

Every point on the boundary of the square has Manhattan distance $1$ from the origin.

Similarly, consider plotting all points in the Cartesian coordinate system whose Chebyshev distance from the origin is $1$.

The formula gives $\max(|x|,|y|)=1$.

Expanding the expression likewise gives $4$ line segments:

Plotting them in the Cartesian coordinate system gives a square with side length $2$, as shown below:

Every point on the boundary of the square has Chebyshev distance $1$ from the origin.

Comparing the two figures, we make the surprising observation:

The $2$ squares are similar figures.

Proof

So, could there be a relationship between Manhattan distance and Chebyshev distance?

Let us give a brief proof:

Assume $A(x_1,y_1),B(x_2,y_2)$.

Expanding the absolute values in the Manhattan distance gives four values. The largest of these four values is the sum of two nonnegative numbers, namely the Manhattan distance. Thus, the Manhattan distance between $A,B$ is:

It is easy to see that this is the Chebyshev distance between the points $(x_1 + y_1,x_1 - y_1), (x_2 + y_2,x_2 - y_2)$.

Therefore, transforming every point $(x,y)$ into $(x + y, x - y)$ makes the Chebyshev distance in the new coordinate system equal to the Manhattan distance in the original coordinate system.

Similarly, the Chebyshev distance between $A,B$ is:

This is the Manhattan distance between the points $(\dfrac{x_1 + y_1}{2},\dfrac{x_1 - y_1}{2}), (\dfrac{x_2 + y_2}{2},\dfrac{x_2 - y_2}{2})$.

Therefore, transforming every point $(x,y)$ into $(\dfrac{x + y}{2},\dfrac{x - y}{2})$ makes the Manhattan distance in the new coordinate system equal to the Chebyshev distance in the original coordinate system.

Conclusion

• The Manhattan coordinate system is obtained by rotating the Chebyshev coordinate system by $45^\circ$ and then scaling it to half its original size.
• After transforming a point $(x,y)$ to $(x + y, x - y)$, the Manhattan distance in the original coordinate system equals the Chebyshev distance in the new coordinate system.
• After transforming a point $(x,y)$ to $(\dfrac{x + y}{2},\dfrac{x - y}{2})$, the Chebyshev distance in the original coordinate system equals the Manhattan distance in the new coordinate system.

When a problem asks for Chebyshev or Manhattan distance, we can often transform one into the other. The two distances have different advantages and disadvantages in different problems, so they should be used flexibly.

Examples

P4648 “IOI2007” Pairs of Animals (Manhattan distance to Chebyshev distance)

P3964 “TJOI2013” Squirrel Gathering (Chebyshev distance to Manhattan distance)

Here is a second solution to P5098 “USACO04OPEN” Cave Cows 3:

We transform the Manhattan distance requested by the problem into Chebyshev distance, changing each point's coordinates $(x,y)$ to $(x + y, x - y)$.

The answer becomes $\max\limits_{i,j\in n}\begin{Bmatrix} \max\begin{Bmatrix} |x_i - x_j|,|y_i - y_j|\end{Bmatrix}\end{Bmatrix}$.

To maximize the differences between the x-coordinates and between the y-coordinates, it is enough to precompute the maximum and minimum values of $x,y$.

#include <algorithm>
#include <cstdio>
using namespace std;

int main() {
  int n, x, y, a, b, minx = 0x7fffffff, maxx = 0, miny = 0x7fffffff, maxy = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", &a, &b);
    x = a + b, y = a - b;
    minx = min(minx, x), maxx = max(maxx, x);
    miny = min(miny, y), maxy = max(maxy, y);
  }
  printf("%d\n", max(maxx - minx, maxy - miny));
  return 0;
}

minx = 0x7FFFFFFF
maxx = 0
miny = 0x7FFFFFFF
maxy = 0
n = int(input())
for i in range(1, n + 1):
    a, b = map(lambda x: int(x), input().split())
    x = a + b
    y = a - b
    minx = min(minx, x)
    maxx = max(maxx, x)
    miny = min(miny, y)
    maxy = max(maxy, y)
print(max(maxx - minx, maxy - miny))

Comparing the two pieces of code, we can see that code produced by these two different approaches is completely equivalent. Amazing, isn't it? More advanced topics require further study.

Minkowski Distance

We define, in $n$-dimensional space, two points $X(x_1, x_2, \dots, x_n)$ and $Y(y_1, y_2, \dots, y_n)$, and their Minkowski distance as:

In particular:

1. When $p=1$, $D(X, Y) = \sum_{i=1}^n \left\vert x_i - y_i \right\vert$ is the Manhattan distance;
2. When $p=2$, $D(X, Y) = \left(\sum_{i=1}^n (x_i - y_i)^2\right)^{1/2}$ is the Euclidean distance;
3. When $p \to \infty$, $D(X, Y) = \lim_{p \to \infty}\left(\sum_{i=1}^n \left\vert x_i - y_i \right\vert ^p\right) ^{1/p} = \max\limits_{i=1}^n \left\vert x_i - y_i \right\vert$ is the Chebyshev distance.

Note that Minkowski distance is a metric only when $p \ge 1$; see Minkowski distance - Wikipedia for a proof.

References and Links

1. A Brief Discussion of Three Common Distance Algorithms, with thanks to the author xuxing for permission.