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

How does a dynamic QR code work?

Is it possible to map the firing of neurons in the human brain so as to stimulate artificial memories in someone else?

Why didn't Boeing produce its own regional jet?

OP Amp not amplifying audio signal

Where would I need my direct neural interface to be implanted?

How exploitable/balanced is this homebrew spell: Spell Permanency?

Is it possible to create a QR code using text?

What is the fastest integer factorization to break RSA?

Avoiding the "not like other girls" trope?

Theorists sure want true answers to this!

Am I breaking OOP practice with this architecture?

Why is the sentence "Das ist eine Nase" correct?

Knowledge-based authentication using Domain-driven Design in C#

Can someone clarify Hamming's notion of important problems in relation to modern academia?

Is it "common practice in Fourier transform spectroscopy to multiply the measured interferogram by an apodizing function"? If so, why?

Using "tail" to follow a file without displaying the most recent lines

How seriously should I take size and weight limits of hand luggage?

What Exploit Are These User Agents Trying to Use?

Car headlights in a world without electricity

How could indestructible materials be used in power generation?

Finding the error in an argument

how do we prove that a sum of two periods is still a period?

How obscure is the use of 令 in 令和?

Notepad++ delete until colon for every line with replace all



Can someone explain this formula for calculating Manhattan distance?


Minimizing the maximum Manhattan distance













5












$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







New contributor




Eugene Yarmash is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$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
    2 days ago






  • 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
    2 days ago











  • $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
    2 days ago
















5












$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







New contributor




Eugene Yarmash is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$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
    2 days ago






  • 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
    2 days ago











  • $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
    2 days ago














5












5








5





$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







New contributor




Eugene Yarmash is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$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







New contributor




Eugene Yarmash is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question







New contributor




Eugene Yarmash is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question






New contributor




Eugene Yarmash is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 2 days ago









Eugene YarmashEugene Yarmash

1284




1284




New contributor




Eugene Yarmash is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Eugene Yarmash is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Eugene Yarmash is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







  • 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
    2 days ago






  • 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
    2 days ago











  • $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
    2 days ago













  • 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
    2 days ago






  • 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
    2 days ago











  • $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
    2 days ago








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
2 days ago




$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
2 days ago




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
2 days ago





$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
2 days ago













$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
2 days ago





$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
2 days ago











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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago












Your Answer





StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

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
);



);






Eugene Yarmash is a new contributor. Be nice, and check out our Code of Conduct.









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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago
















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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago














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 2 days ago









Apass.JackApass.Jack

13.8k1940




13.8k1940







  • 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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago













  • 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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago










  • $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
    2 days ago








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
2 days ago




$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
2 days ago












$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
2 days ago




$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
2 days ago












$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
2 days ago




$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
2 days ago












$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
2 days ago




$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
2 days ago












$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
2 days ago





$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
2 days ago











Eugene Yarmash is a new contributor. Be nice, and check out our Code of Conduct.









draft saved

draft discarded


















Eugene Yarmash is a new contributor. Be nice, and check out our Code of Conduct.












Eugene Yarmash is a new contributor. Be nice, and check out our Code of Conduct.











Eugene Yarmash is a new contributor. Be nice, and check out our Code of Conduct.














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

រឿង រ៉ូមេអូ និង ហ្ស៊ុយលីយេ សង្ខេបរឿង តួអង្គ បញ្ជីណែនាំ

Crop image to path created in TikZ? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Crop an inserted image?TikZ pictures does not appear in posterImage behind and beyond crop marks?Tikz picture as large as possible on A4 PageTransparency vs image compression dilemmaHow to crop background from image automatically?Image does not cropTikzexternal capturing crop marks when externalizing pgfplots?How to include image path that contains a dollar signCrop image with left size given

Romeo and Juliet ContentsCharactersSynopsisSourcesDate and textThemes and motifsCriticism and interpretationLegacyScene by sceneSee alsoNotes and referencesSourcesExternal linksNavigation menu"Consumer Price Index (estimate) 1800–"10.2307/28710160037-3222287101610.1093/res/II.5.31910.2307/45967845967810.2307/2869925286992510.1525/jams.1982.35.3.03a00050"Dada Masilo: South African dancer who breaks the rules"10.1093/res/os-XV.57.1610.2307/28680942868094"Sweet Sorrow: Mann-Korman's Romeo and Juliet Closes Sept. 5 at MN's Ordway"the original10.2307/45957745957710.1017/CCOL0521570476.009"Ram Leela box office collections hit massive Rs 100 crore, pulverises prediction"Archived"Broadway Revival of Romeo and Juliet, Starring Orlando Bloom and Condola Rashad, Will Close Dec. 8"Archived10.1075/jhp.7.1.04hon"Wherefore art thou, Romeo? To make us laugh at Navy Pier"the original10.1093/gmo/9781561592630.article.O006772"Ram-leela Review Roundup: Critics Hail Film as Best Adaptation of Romeo and Juliet"Archived10.2307/31946310047-77293194631"Romeo and Juliet get Twitter treatment""Juliet's Nurse by Lois Leveen""Romeo and Juliet: Orlando Bloom's Broadway Debut Released in Theaters for Valentine's Day"Archived"Romeo and Juliet Has No Balcony"10.1093/gmo/9781561592630.article.O00778110.2307/2867423286742310.1076/enst.82.2.115.959510.1080/00138380601042675"A plague o' both your houses: error in GCSE exam paper forces apology""Juliet of the Five O'Clock Shadow, and Other Wonders"10.2307/33912430027-4321339124310.2307/28487440038-7134284874410.2307/29123140149-661129123144728341M"Weekender Guide: Shakespeare on The Drive""balcony"UK public library membership"romeo"UK public library membership10.1017/CCOL9780521844291"Post-Zionist Critique on Israel and the Palestinians Part III: Popular Culture"10.2307/25379071533-86140377-919X2537907"Capulets and Montagues: UK exam board admit mixing names up in Romeo and Juliet paper"Istoria Novellamente Ritrovata di Due Nobili Amanti2027/mdp.390150822329610820-750X"GCSE exam error: Board accidentally rewrites Shakespeare"10.2307/29176390149-66112917639"Exam board apologises after error in English GCSE paper which confused characters in Shakespeare's Romeo and Juliet""From Mariotto and Ganozza to Romeo and Guilietta: Metamorphoses of a Renaissance Tale"10.2307/37323537323510.2307/2867455286745510.2307/28678912867891"10 Questions for Taylor Swift"10.2307/28680922868092"Haymarket Theatre""The Zeffirelli Way: Revealing Talk by Florentine Director""Michael Smuin: 1938-2007 / Prolific dance director had showy career"The Life and Art of Edwin BoothRomeo and JulietRomeo and JulietRomeo and JulietRomeo and JulietEasy Read Romeo and JulietRomeo and Julieteeecb12003684p(data)4099369-3n8211610759dbe00d-a9e2-41a3-b2c1-977dd692899302814385X313670221313670221