Skip to content

Distance

Euclidean Distance

Two-Dimensional Space

Definition

Euclidean distance, also commonly referred to as Euclidean distance. In a plane Cartesian coordinate system, let the coordinates of points \(A\) and \(B\) be \(A(x_1,y_1)\) and \(B(x_2,y_2)\) respectively. Then the Euclidean distance between the two points is:

\[ \left | AB \right | = \sqrt{\left ( x_2 - x_1 \right )^2 + \left ( y_2 - y_1 \right )^2} \]

Explanation

For example, in a plane Cartesian coordinate system, given two points \(A(6,5)\) and \(B(2,2)\), we can easily compute the Euclidean distance between \(A\) and \(B\) using the formula:

\[ \left | AB \right | = \sqrt{\left ( 2 - 6 \right )^2 + \left ( 2 - 5 \right )^2} = \sqrt{4^2+3^2} = 5 \]

Additionally, the Euclidean distance from a point \(P(x,y)\) to the origin can be expressed as:

\[ |P| = \sqrt{x^2+y^2} \]

n-Dimensional Space

Introduction

What about the Euclidean distance formula for two points in three-dimensional space? Let's examine the following diagram.

dis-3-dimensional

We can easily observe that in \(\triangle ADC\), \(\angle ADC = 90^\circ\); and in \(\triangle ACB\), \(\angle ACB = 90^\circ\).

\[ \begin{aligned} \therefore ~ |AB| &= \sqrt{|AC|^2+|BC|^2} \\ &= \sqrt{|AD|^2+|CD|^2+|BC|^2} \end{aligned} \]

Definition

Thus, the distance formula for Euclidean distance in three-dimensional space is:

\[ \begin{gathered} \left | AB \right | = \sqrt{\left ( x_2 - x_1 \right )^2 + \left ( y_2 - y_1 \right )^2 + \left ( z_2 - z_1 \right )^2} \\ |P| = \sqrt{x^2+y^2+z^2} \end{gathered} \]

Explanation

NOIP2017 Senior Group: Cheese utilizes this knowledge and can serve as an example problem for Euclidean distance.

By extension, we obtain the distance formula for Euclidean distance in \(n\)-dimensional space: For vectors \(\vec A(x_{11}, x_{12}, \cdots,x_{1n})\) and \(\vec B(x_{21}, x_{22}, \cdots,x_{2n})\), we have

\[ \begin{aligned} \lVert\overrightarrow{AB}\rVert &= \sqrt{\left ( x_{11} - x_{21} \right )^2 + \left ( x_{12} - x_{22} \right )^2 + \cdot \cdot \cdot +\left ( x_{1n} - x_{2n} \right )^2}\\ &= \sqrt{\sum_{i = 1}^{n}(x_{1i} - x_{2i})^2} \end{aligned} \]

Although Euclidean distance is very useful, it also has notable drawbacks. When computing the Euclidean distance between two integer points, the result is often a floating-point number, which can introduce some error.

Manhattan Distance

Definition

In two-dimensional space, the Manhattan distance (also known as Manhattan distance) between two points is the sum of the absolute differences of their x-coordinates and y-coordinates. Let points \(A(x_1,y_1)\) and \(B(x_2,y_2)\). Then the Manhattan distance between \(A\) and \(B\) can be expressed by the formula:

\[ d(A,B) = |x_1 - x_2| + |y_1 - y_2| \]

Explanation

Observe the following diagram:

manhattan-dis-diff

Between \(A\) and \(B\), the yellow and orange lines represent Manhattan distances, while the red and blue lines represent equivalent Manhattan distances. The green line represents the Euclidean distance.

Using the same example, in the diagram below, the coordinates of \(A\) and \(B\) are \(A(25,20)\) and \(B(10,10)\) respectively.

manhattan-dis

Using the formula, we can easily compute the Manhattan distance between \(A\) and \(B\):

\[ d(A,B) = |20 - 10| + |25 - 10| = 10 + 15 = 25 \]

Through derivation, we obtain the Manhattan distance formula for \(n\)-dimensional space:

\[ \begin{aligned} d(A,B) &= |x_1 - y_1| + |x_2 - y_2| + \cdot \cdot \cdot + |x_n - y_n|\\ &= \sum_{i = 1}^{n}|x_i - y_i| \end{aligned} \]

Properties

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

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

Example Problem

P5098 "USACO04OPEN" Cave Cows 3

According to the problem statement, for the expression \(|x_1-x_2|+|y_1-y_2|\), we can assume \(x_1 - x_2 \geq 0\) and consider two cases based on 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 simply computing the maximum and minimum values of \(x+y\) and \(x-y\) respectively.

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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))

Actually, there is a second approach: converting Manhattan distance to Chebyshev distance for solving, which will be discussed in the final section.

Chebyshev Distance

Definition

Chebyshev distance is a metric in vector space, defined as the maximum of the absolute differences between the coordinates of two points.1

In two-dimensional space, the Chebyshev distance between two points is the maximum of the absolute differences of their x-coordinates and y-coordinates. Let points \(A(x_1,y_1)\) and \(B(x_2,y_2)\). Then the Chebyshev distance between \(A\) and \(B\) can be expressed by the formula:

\[ d(A,B) = \max(|x_1 - x_2|, |y_1 - y_2|) \]

The distance formula for Chebyshev distance in \(n\)-dimensional space can be expressed as:

\[ \begin{aligned} d(x,y) &= \max\begin{Bmatrix} |x_1 - y_1|,|x_2 - y_2|,\cdot \cdot \cdot,|x_n - y_n|\end{Bmatrix} \\ &= \max\begin{Bmatrix} |x_i - y_i|\end{Bmatrix}(i \in [1, n])\end{aligned} \]

Explanation

Using the same example, in the diagram below, the coordinates of \(A\) and \(B\) are \(A(25,20)\) and \(B(10,10)\) respectively.

Chebyshev-dis

\[ d(A,B) = \max(|20 - 10|, |25 - 10|) = \max(10, 15) = 15 \]

Interconversion between Manhattan Distance and Chebyshev Distance

Process

First, consider plotting all points in the plane Cartesian coordinate system whose Manhattan distance to the origin is \(1\).

Using the formula, we easily obtain the equation \(|x| + |y| = 1\).

Expanding the absolute values yields four linear functions:

\[ \begin{aligned} &y = -x + 1 &(x \geq 0, y \geq 0) \\ &y = x + 1 &(x \leq 0, y \geq 0) \\ &y = x - 1 &(x \geq 0, y \leq 0) \\ &y = -x - 1 &(x \leq 0, y \leq 0) \\ \end{aligned} \]

Plotting these four functions on the Cartesian plane yields a square with side length \(\sqrt{2}\), as shown below:

dis-diff-square-1

All points on the boundary of this square have a Manhattan distance of \(1\) to the origin.

Similarly, consider plotting all points in the plane Cartesian coordinate system whose Chebyshev distance to the origin is \(1\).

From the formula, we know \(\max(|x|,|y|)=1\).

Expanding this expression also yields four line segments:

\[ \begin{aligned} &y = 1&(-1\leq x \leq 1) \\ &y = -1&(-1\leq x \leq 1) \\ &x = 1,&(-1\leq y \leq 1) \\ &x = -1,&(-1\leq y \leq 1) \\ \end{aligned} \]

Plotting these on the Cartesian plane yields a square with side length \(2\), as shown below:

dis-diff-square-2

All points on the boundary of this square have a Chebyshev distance of \(1\) to the origin.

Comparing these two diagrams, we observe a remarkable fact:

These two squares are similar figures.

Proof

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

Let's provide a brief proof:

Assume \(A(x_1,y_1),B(x_2,y_2)\),

Expanding the absolute values in the Manhattan distance yields four values, the maximum of which is the sum of two non-negative numbers, i.e., the Manhattan distance. The Manhattan distance between \(A\) and \(B\) is:

\[ \begin{aligned} d(A,B)&=|x_1 - x_2| + |y_1 - y_2|\\ &=\max\begin{Bmatrix} x_1 - x_2 + y_1 - y_2, x_1 - x_2 + y_2 - y_1,x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1\end{Bmatrix}\\ &= \max(|(x_1 + y_1) - (x_2 + y_2)|, |(x_1 - y_1) - (x_2 - y_2)|) \end{aligned} \]

We can easily see that this is the Chebyshev distance between the points \((x_1 + y_1,x_1 - y_1)\) and \((x_2 + y_2,x_2 - y_2)\).

Therefore, transforming each point \((x,y)\) to \((x + y, x - y)\), the Chebyshev distance in the new coordinate system equals the Manhattan distance in the original coordinate system.

Similarly, the Chebyshev distance between \(A\) and \(B\) is:

\[ \begin{aligned} d(A,B)&=\max\begin{Bmatrix} |x_1 - x_2|,|y_1 - y_2|\end{Bmatrix}\\ &=\max\begin{Bmatrix} \left|\dfrac{x_1 + y_1}{2}-\dfrac{x_2 + y_2}{2}\right|+\left|\dfrac{x_1 - y_1}{2}-\dfrac{x_2 - y_2}{2}\right|\end{Bmatrix} \end{aligned} \]

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

Therefore, transforming each point \((x,y)\) to \((\dfrac{x + y}{2},\dfrac{x - y}{2})\), the Manhattan distance in the new coordinate system equals 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 down by half.
  • Transforming a point \((x,y)\) to \((x + y, x - y)\) makes the Manhattan distance in the original coordinate system equal to the Chebyshev distance in the new coordinate system.
  • Transforming a point \((x,y)\) to \((\dfrac{x + y}{2},\dfrac{x - y}{2})\) makes the Chebyshev distance in the original coordinate system equal to the Manhattan distance in the new coordinate system.

When encountering problems involving Chebyshev distance or Manhattan distance, we can often convert between them to find a solution. The two distances have different advantages and disadvantages in different problems, and should be applied flexibly.

Example Problems

P4648 "IOI2007" pairs Animal Pairs (Manhattan distance to Chebyshev distance)

P3964 "TJOI2013" Squirrel Gathering (Chebyshev distance to Manhattan distance)

Finally, here is the second solution for P5098 "USACO04OPEN" Cave Cows 3:

We consider converting the Manhattan distance required by the problem into Chebyshev distance, i.e., transforming each point's coordinates \((x,y)\) to \((x + y, x - y)\).

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

Now, to maximize the differences in x-coordinates and y-coordinates, we only need to precompute the maximum and minimum values of \(x\) and \(y\).

Reference Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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 code snippets, we can see that two different approaches lead to completely equivalent code. Isn't that fascinating? Of course, more advanced topics require further independent study.

Minkowski Distance

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

\[ D(X, Y) = \left(\sum_{i=1}^n \left\vert x_i - y_i \right\vert ^p\right)^{\frac{1}{p}}. \]

Specifically:

  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: Minkowski distance is a metric only when \(p \ge 1\). For proof, refer to Minkowski distance - Wikipedia.

  1. A Brief Discussion on Three Common Distance Algorithms, with thanks to author xuxing for authorization.

  1. Chebyshev distance - Wikipedia, the free encyclopedia ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用