Can someone explain this formula for calculating Manhattan distance?Minimizing the maximum Manhattan distance

Will 700 more planes a day fly because of the Heathrow expansion?

Prove that a definite integral is an infinite sum

How can I get people to remember my character's gender?

How do I calculate how many of an item I'll have in this inventory system?

How to pass hash as password to ssh server

Find magical solution to magical equation

Correct way of drawing empty, half-filled and fully filled circles?

Definition of conditional probability and a problem.

Snap victim memorial reference in Avengers: Endgame

3D Volume in TIKZ

Is there a word that describes the unjustified use of a more complex word?

How can internet speed be 10 times slower without a router than when using a router?

A factorization game

Manager is threatening to grade me poorly if I don't complete the project

Outlining A Novel - How do you make it less of a slog?

Why did the Apollo 13 crew extend the LM landing gear?

Extra space in cells when using token lists to build tabular content

Can my 2 children, aged 10 and 12, who are US citizens, travel to the USA on expired American passports?

Gladys unchained

Python 3 - simple temperature program

Are there terms in German for different skull shapes?

Should I mention being denied entry to UK due to a confusion in my Visa and Ticket bookings?

Should I simplify my writing in a foreign country?

How should I tell my manager I'm not paying for an optional after work event I'm not going to?



Can someone explain this formula for calculating Manhattan distance?


Minimizing the maximum Manhattan distance













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?










share|cite|improve this question









$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$


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?










share|cite|improve this question









$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












6








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?










share|cite|improve this question









$endgroup$




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?







square-grid






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Mar 31 at 13:07









Eugene YarmashEugene Yarmash

1334




1334







  • 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













  • 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








1




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




$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




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$
@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





$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











1 Answer
1






active

oldest

votes


















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
$$beginaligned
|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|)
endaligned$$



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




  • $age 0$


    • $bgt 0$. LHS is $a+b$, RHS is $a+b$.


    • $ble 0$. LHS is $a-b$, RHS is $a-b$.



  • $alt 0$


    • $bgt 0$. LHS is $-a+b$, RHS is $-(a-b)$.


    • $ble 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.








share|cite|improve this answer









$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








StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);













draft saved

draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106289%2fcan-someone-explain-this-formula-for-calculating-manhattan-distance%23new-answer', 'question_page');

);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









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
$$beginaligned
|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|)
endaligned$$



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




  • $age 0$


    • $bgt 0$. LHS is $a+b$, RHS is $a+b$.


    • $ble 0$. LHS is $a-b$, RHS is $a-b$.



  • $alt 0$


    • $bgt 0$. LHS is $-a+b$, RHS is $-(a-b)$.


    • $ble 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.








share|cite|improve this answer









$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
















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
$$beginaligned
|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|)
endaligned$$



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




  • $age 0$


    • $bgt 0$. LHS is $a+b$, RHS is $a+b$.


    • $ble 0$. LHS is $a-b$, RHS is $a-b$.



  • $alt 0$


    • $bgt 0$. LHS is $-a+b$, RHS is $-(a-b)$.


    • $ble 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.








share|cite|improve this answer









$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














6












6








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
$$beginaligned
|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|)
endaligned$$



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




  • $age 0$


    • $bgt 0$. LHS is $a+b$, RHS is $a+b$.


    • $ble 0$. LHS is $a-b$, RHS is $a-b$.



  • $alt 0$


    • $bgt 0$. LHS is $-a+b$, RHS is $-(a-b)$.


    • $ble 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.








share|cite|improve this answer









$endgroup$



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
$$beginaligned
|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|)
endaligned$$



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




  • $age 0$


    • $bgt 0$. LHS is $a+b$, RHS is $a+b$.


    • $ble 0$. LHS is $a-b$, RHS is $a-b$.



  • $alt 0$


    • $bgt 0$. LHS is $-a+b$, RHS is $-(a-b)$.


    • $ble 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.









share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Mar 31 at 14:42









Apass.JackApass.Jack

14.8k1941




14.8k1941







  • 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













  • 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








2




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$
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$
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 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$
@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





$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


















draft saved

draft discarded
















































Thanks for contributing an answer to Computer Science Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid


  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f106289%2fcan-someone-explain-this-formula-for-calculating-manhattan-distance%23new-answer', 'question_page');

);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Færeyskur hestur Heimild | Tengill | Tilvísanir | LeiðsagnarvalRossið - síða um færeyska hrossið á færeyskuGott ár hjá færeyska hestinum

He _____ here since 1970 . Answer needed [closed]What does “since he was so high” mean?Meaning of “catch birds for”?How do I ensure “since” takes the meaning I want?“Who cares here” meaningWhat does “right round toward” mean?the time tense (had now been detected)What does the phrase “ring around the roses” mean here?Correct usage of “visited upon”Meaning of “foiled rail sabotage bid”It was the third time I had gone to Rome or It is the third time I had been to Rome

Slayer Innehåll Historia | Stil, komposition och lyrik | Bandets betydelse och framgångar | Sidoprojekt och samarbeten | Kontroverser | Medlemmar | Utmärkelser och nomineringar | Turnéer och festivaler | Diskografi | Referenser | Externa länkar | Navigeringsmenywww.slayer.net”Metal Massacre vol. 1””Metal Massacre vol. 3””Metal Massacre Volume III””Show No Mercy””Haunting the Chapel””Live Undead””Hell Awaits””Reign in Blood””Reign in Blood””Gold & Platinum – Reign in Blood””Golden Gods Awards Winners”originalet”Kerrang! Hall Of Fame””Slayer Looks Back On 37-Year Career In New Video Series: Part Two””South of Heaven””Gold & Platinum – South of Heaven””Seasons in the Abyss””Gold & Platinum - Seasons in the Abyss””Divine Intervention””Divine Intervention - Release group by Slayer””Gold & Platinum - Divine Intervention””Live Intrusion””Undisputed Attitude””Abolish Government/Superficial Love””Release “Slatanic Slaughter: A Tribute to Slayer” by Various Artists””Diabolus in Musica””Soundtrack to the Apocalypse””God Hates Us All””Systematic - Relationships””War at the Warfield””Gold & Platinum - War at the Warfield””Soundtrack to the Apocalypse””Gold & Platinum - Still Reigning””Metallica, Slayer, Iron Mauden Among Winners At Metal Hammer Awards””Eternal Pyre””Eternal Pyre - Slayer release group””Eternal Pyre””Metal Storm Awards 2006””Kerrang! Hall Of Fame””Slayer Wins 'Best Metal' Grammy Award””Slayer Guitarist Jeff Hanneman Dies””Bullet-For My Valentine booed at Metal Hammer Golden Gods Awards””Unholy Aliance””The End Of Slayer?””Slayer: We Could Thrash Out Two More Albums If We're Fast Enough...””'The Unholy Alliance: Chapter III' UK Dates Added”originalet”Megadeth And Slayer To Co-Headline 'Canadian Carnage' Trek”originalet”World Painted Blood””Release “World Painted Blood” by Slayer””Metallica Heading To Cinemas””Slayer, Megadeth To Join Forces For 'European Carnage' Tour - Dec. 18, 2010”originalet”Slayer's Hanneman Contracts Acute Infection; Band To Bring In Guest Guitarist””Cannibal Corpse's Pat O'Brien Will Step In As Slayer's Guest Guitarist”originalet”Slayer’s Jeff Hanneman Dead at 49””Dave Lombardo Says He Made Only $67,000 In 2011 While Touring With Slayer””Slayer: We Do Not Agree With Dave Lombardo's Substance Or Timeline Of Events””Slayer Welcomes Drummer Paul Bostaph Back To The Fold””Slayer Hope to Unveil Never-Before-Heard Jeff Hanneman Material on Next Album””Slayer Debut New Song 'Implode' During Surprise Golden Gods Appearance””Release group Repentless by Slayer””Repentless - Slayer - Credits””Slayer””Metal Storm Awards 2015””Slayer - to release comic book "Repentless #1"””Slayer To Release 'Repentless' 6.66" Vinyl Box Set””BREAKING NEWS: Slayer Announce Farewell Tour””Slayer Recruit Lamb of God, Anthrax, Behemoth + Testament for Final Tour””Slayer lägger ner efter 37 år””Slayer Announces Second North American Leg Of 'Final' Tour””Final World Tour””Slayer Announces Final European Tour With Lamb of God, Anthrax And Obituary””Slayer To Tour Europe With Lamb of God, Anthrax And Obituary””Slayer To Play 'Last French Show Ever' At Next Year's Hellfst””Slayer's Final World Tour Will Extend Into 2019””Death Angel's Rob Cavestany On Slayer's 'Farewell' Tour: 'Some Of Us Could See This Coming'””Testament Has No Plans To Retire Anytime Soon, Says Chuck Billy””Anthrax's Scott Ian On Slayer's 'Farewell' Tour Plans: 'I Was Surprised And I Wasn't Surprised'””Slayer””Slayer's Morbid Schlock””Review/Rock; For Slayer, the Mania Is the Message””Slayer - Biography””Slayer - Reign In Blood”originalet”Dave Lombardo””An exclusive oral history of Slayer”originalet”Exclusive! Interview With Slayer Guitarist Jeff Hanneman”originalet”Thinking Out Loud: Slayer's Kerry King on hair metal, Satan and being polite””Slayer Lyrics””Slayer - Biography””Most influential artists for extreme metal music””Slayer - Reign in Blood””Slayer guitarist Jeff Hanneman dies aged 49””Slatanic Slaughter: A Tribute to Slayer””Gateway to Hell: A Tribute to Slayer””Covered In Blood””Slayer: The Origins of Thrash in San Francisco, CA.””Why They Rule - #6 Slayer”originalet”Guitar World's 100 Greatest Heavy Metal Guitarists Of All Time”originalet”The fans have spoken: Slayer comes out on top in readers' polls”originalet”Tribute to Jeff Hanneman (1964-2013)””Lamb Of God Frontman: We Sound Like A Slayer Rip-Off””BEHEMOTH Frontman Pays Tribute To SLAYER's JEFF HANNEMAN””Slayer, Hatebreed Doing Double Duty On This Year's Ozzfest””System of a Down””Lacuna Coil’s Andrea Ferro Talks Influences, Skateboarding, Band Origins + More””Slayer - Reign in Blood””Into The Lungs of Hell””Slayer rules - en utställning om fans””Slayer and Their Fans Slashed Through a No-Holds-Barred Night at Gas Monkey””Home””Slayer””Gold & Platinum - The Big 4 Live from Sofia, Bulgaria””Exclusive! Interview With Slayer Guitarist Kerry King””2008-02-23: Wiltern, Los Angeles, CA, USA””Slayer's Kerry King To Perform With Megadeth Tonight! - Oct. 21, 2010”originalet”Dave Lombardo - Biography”Slayer Case DismissedArkiveradUltimate Classic Rock: Slayer guitarist Jeff Hanneman dead at 49.”Slayer: "We could never do any thing like Some Kind Of Monster..."””Cannibal Corpse'S Pat O'Brien Will Step In As Slayer'S Guest Guitarist | The Official Slayer Site”originalet”Slayer Wins 'Best Metal' Grammy Award””Slayer Guitarist Jeff Hanneman Dies””Kerrang! Awards 2006 Blog: Kerrang! Hall Of Fame””Kerrang! Awards 2013: Kerrang! Legend”originalet”Metallica, Slayer, Iron Maien Among Winners At Metal Hammer Awards””Metal Hammer Golden Gods Awards””Bullet For My Valentine Booed At Metal Hammer Golden Gods Awards””Metal Storm Awards 2006””Metal Storm Awards 2015””Slayer's Concert History””Slayer - Relationships””Slayer - Releases”Slayers officiella webbplatsSlayer på MusicBrainzOfficiell webbplatsSlayerSlayerr1373445760000 0001 1540 47353068615-5086262726cb13906545x(data)6033143kn20030215029