Manhattan distance vs Euclidean distance

Question

Suppose that for two vectors A and B, we know that their Euclidean distance is less than d. What can I say about their Manhattan distance?

Answer 1

HINT: Pick a point $p$ and consider the points on the circle of radius $d$ centred at $p$. Which of them are furthest from $p$ in the Manhattan metric? Everything inside the circle is closer to $p$ in the Manhattan metric than those points.

Added: For the question in your comment take a look at this rough sketch:

Certainly $d_1<d_2$; how do $m_1$ and $m_2$ compare? (If you need numbers, those could be the points $\langle 1,0\rangle$ for $p_2$ and $\langle\frac35,\frac35\rangle$ for $p_1$, for instance.)

Answer 2

Hint: $$ \overbrace{(\Delta x)^2+(\Delta y)^2}^{\begin{array}{c}\text{square of the}\\\text{ Euclidean distance}\end{array}}\le(\Delta x)^2+2|\Delta x\Delta y|+(\Delta y)^2=\overbrace{(|\Delta x|+|\Delta y|)^2}^{\begin{array}{c}\text{square of the}\\\text{ Manhattan distance}\end{array}}\tag{1} $$ Furthermore, since the square of a real number is non-negative, $$ (\Delta x)^2-2|\Delta x\Delta y|+(\Delta y)^2=(|\Delta x|-|\Delta y|)^2\ge0\tag{2} $$ we can add $(|\Delta x|+|\Delta y|)^2$ to both sides of $(2)$ to get $$ 2\overbrace{\left[(\Delta x)^2+(\Delta y)^2\right]}^{\begin{array}{c}\text{square of the}\\\text{ Euclidean distance}\end{array}}\ge\overbrace{(|\Delta x|+|\Delta y|)^2}^{\begin{array}{c}\text{square of the}\\\text{ Manhattan distance}\end{array}}\tag{3} $$

Answer 3

In $n$ dimensional space, Given a Euclidean distance $d$, the Manhattan distance $M$ is :

• Maximized when $A$ and $B$ are 2 corners of a hypercube
• Minimized when $A$ and $B$ are equal in every dimension but 1 (they lie along a line parallel to an axis)

In the hypercube case, let the side length of the cube be $s$. Then $sn = M$ and $s^2 + s^2 + s^2 \dots = d^2$, so $n(M/n)^2 = d^2$, or $M = d\sqrt{n}$.

In the line case, $M = d$.

So given $d$, you can infer $d < M < d\sqrt{n}$.

And if you are only given that $d$ is the upper bound of the Euclidean distance, then you can only infer that $M < d\sqrt{n}$, and no lower bound can be inferred.