Can someone explain this formula for calculating Manhattan distance?Minimizing the maximum Manhattan distance
Using "tail" to follow a file without displaying the most recent lines
In Bayesian inference, why are some terms dropped from the posterior predictive?
Is it a bad idea to plug the other end of ESD strap to wall ground?
Processor speed limited at 0.4 Ghz
Implication of namely
Is it possible to create a QR code using text?
Sums of two squares in arithmetic progressions
My ex-girlfriend uses my Apple ID to log in to her iPad. Do I have to give her my Apple ID password to reset it?
What are the G forces leaving Earth orbit?
Avoiding the "not like other girls" trope?
What is an equivalently powerful replacement spell for the Yuan-Ti's Suggestion spell?
How to travel to Japan while expressing milk?
Is there a hemisphere-neutral way of specifying a season?
How to find if SQL server backup is encrypted with TDE without restoring the backup
Can someone clarify Hamming's notion of important problems in relation to modern academia?
How could indestructible materials be used in power generation?
What exactly is ineptocracy?
How to install cross-compiler on Ubuntu 18.04?
Send out email when Apex Queueable fails and test it
How to show a landlord what we have in savings?
If a warlock makes a Dancing Sword their pact weapon, is there a way to prevent it from disappearing if it's farther away for more than a minute?
How to stretch the corners of this image so that it looks like a perfect rectangle?
Mathematica command that allows it to read my intentions
How exploitable/balanced is this homebrew spell: Spell Permanency?
Can someone explain this formula for calculating Manhattan distance?
Minimizing the maximum Manhattan distance
$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?
square-grid
asked 2 days ago
Eugene YarmashEugene Yarmash
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.
$endgroup$
add a comment |
$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?
square-grid
asked 2 days ago
Eugene YarmashEugene Yarmash
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.
$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
add a comment |
$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?
square-grid
asked 2 days ago
Eugene YarmashEugene Yarmash
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.
$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
square-grid
asked 2 days ago
Eugene YarmashEugene Yarmash
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.
asked 2 days ago
Eugene YarmashEugene Yarmash
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.
asked 2 days ago
Eugene YarmashEugene Yarmash
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.
asked 2 days ago
Eugene YarmashEugene Yarmash
1284
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
add a comment |
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
add a comment |
1 Answer
1
active
oldest
votes
$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.
answered 2 days ago
Apass.JackApass.Jack
13.8k1940
$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 formulabased 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
|
show 1 more comment
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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.
answered 2 days ago
Apass.JackApass.Jack
13.8k1940
$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 formulabased 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
|
show 1 more comment
$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.
answered 2 days ago
Apass.JackApass.Jack
13.8k1940
$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 formulabased 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
|
show 1 more comment
$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.
answered 2 days ago
Apass.JackApass.Jack
13.8k1940
$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.
answered 2 days ago
Apass.JackApass.Jack
13.8k1940
answered 2 days ago
Apass.JackApass.Jack
13.8k1940
answered 2 days ago
Apass.JackApass.Jack
13.8k1940
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 formulabased 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
|
show 1 more comment
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 formulabased 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
|
show 1 more comment
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.
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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