Manhattan distance vs Euclidean distance 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?
 A: 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.)
A: 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}
$$
A: 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.
