6
$\begingroup$

This is from a Kickstart problem:

Note: The Manhattan distance between two squares (r1,c1) and (r2,c2) is defined as |r1 - r2| + |c1 - c2|, where |*| operator denotes the absolute value.

Then in the analysis:

Note that the manhattan distance has an equivalent formula:

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))

This formula is based on the fact that for any point, the set of points within a manhattan distance of K form a square rotated by 45 degrees. The benefit of this formula is that if we fix (x2, y2), the distance will be maximized when x1 + y1 and x1 - y1 are either maximized or minimized.

Could someone explain in more details how this formula can be derived?

$\endgroup$
  • 1
    $\begingroup$ Why don't you try drawing this square, and determine what these distances represent? Hint: try to determine the coordinates of the corners of this square. $\endgroup$ – Discrete lizard Mar 31 at 13:32
  • 1
    $\begingroup$ @DavidRicherby The benefit appears to be that for the specific use-case of determining whether there exists a point with distance at most $k$ to some set $S$, it seems we can do this more efficiently, as we only have to find the maximum and minimum of the points in $S$ according to $x_1+y_1$ and $x_1-y_1$ once and then can query for each point in constant time. Do you think there is an easier way to get a constant query time here? $\endgroup$ – Discrete lizard Mar 31 at 13:44
  • $\begingroup$ I suppose that you could also directly look at the corners of the smallest enclosing 45 degree turned square of these points, and then you end up with basically the same values as the maxima and minima in your dataset. So, in a way, I see that changing the Manhattan distance itself could be a rather complicated way of achieving this. $\endgroup$ – Discrete lizard Mar 31 at 13:51
6
$\begingroup$

Lemma. $|a|+|b|=\max(|a+b|, |a-b|)$ for any real number $a$ and $b$.

Proof 1. $|x|=\max(x, -x)$ for all real number $x$. So $$\begin{aligned} |a|+|b| &=\max(a, -a) + \max(b, -b)\\ &=\max(a+b, a-b, -a+b, -a-b)\\ &=\max(\max(a+b, -a-b), \max(a-b, -(a-b))\\ &=\max(|a+b|, |a-b|) \end{aligned}$$

Proof 2. There are $2 \times 2 = 4$ cases.

  • $a\ge 0$
    • $b\gt 0$. LHS is $a+b$, RHS is $a+b$.
    • $b\le 0$. LHS is $a-b$, RHS is $a-b$.
  • $a\lt 0$
    • $b\gt 0$. LHS is $-a+b$, RHS is $-(a-b)$.
    • $b\le 0$. LHS is $-a-b$, RHS is $-(a+b)$.

One dimensionality of Manhattan-distance.

The Manhattan-distance of two points $(x_1, y_1)$ and $(x_2, y_2)$ is either $|(x_1+y_1)-(x_2+y_2)|$ or $|(x_1-y_1)-(x_2-y_2)|$, whichever is larger. That is, $ d((x_1, y_1),(x_2, y_2))= \max(|(x_1+y_1)-(x_2+y_2)|, |(x_1-y_1)-(x_2-y_2)|)$$

Proof: By definition,
$$d((x_1, y_1),(x_2, y_2))=|x_1-x_2| + |y_1-y_2|.$$ Now apply the lemma above. QED.

This answer also serves as a complement to another answer of mine.

$\endgroup$
  • 2
    $\begingroup$ The one dimensionality of Manhattan-distance is the main trick that is applied in the algorithm, as this allows you to sort according to this distance. $\endgroup$ – Discrete lizard Mar 31 at 15:41
  • $\begingroup$ This is a great explanation, thanks. One question remains though: how is this formula based on the fact that for any point, the set of points within a manhattan distance of K form a square rotated by 45 degrees ? $\endgroup$ – Eugene Yarmash Mar 31 at 16:10
  • $\begingroup$ @EugeneYarmash Let the given point be $(a,b)$. Then a point (x,y) is within $K$ M-distance of $(a,b)$ if and only if $|x+y-(a+b)|\le K$ and $|x-y-(a-b)|\le K$. The points defined by $|x+y-(a+b)|\le K$ is between two parallel lines, $x+y=a+b+K$ and $x+y=a+b-K$, both of which are in 45 degree with the axises. The points defined by $|x-y-(a-b)|\le K$ is between two parallel lines, $x-y=a-b+K$ and $x-y=a-b-K$, both of which are in 45 degree with the axises as well. $\endgroup$ – Apass.Jack Mar 31 at 16:26
  • $\begingroup$ @EugeneYarmash (continued) The Euclidean distance between the first two parallel lines is $\sqrt 2K$, which is also the the Euclidean distance between the second two parallel lines. So we got "a square rotated by 45 degree." By the way, I am explaining the logic the other way around, that is, that fact is based on the formula! I believe, it should be better to say "this formula can be understood intuitively from the fact that ..." instead of "this formula is bases on the fact that ...". $\endgroup$ – Apass.Jack Mar 31 at 16:32
  • $\begingroup$ Images can help understanding a lot (because the super-parallel computation done by human's eyes and brains) but could be deceiving or misleading. A mathematical proof might not be easy to come by or understand but it is much more rigorous. $\endgroup$ – Apass.Jack Mar 31 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.