1
$\begingroup$

I am studying algorithms and datastructures, and in CLRS chapter 33.4, the exercise 33.4-4 states the following:

We can define the distance between two points in ways other than euclidean. In the plan, the $L_m$ distance between points $p_1$ and $p_2$ are given by the expression $(|x_1-x_2|^m+|y_1-y_2|^m)^{1/m}$. euclidean distance, there, is $L_2$-distance. Modify the closest pair algorithm to use the $L_1$-distance, which is also known as the Manhattan distance.

I understand its an easy modification, however when I've been comparing my intuition with that of solutions provided online (e.g. https://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html), all I can find is that they all point to the number of points in the $\delta$ x $2\delta$ is increased to 10 (from 8), adding one point to the middle of both squares formed by the rectangle (here marked with red below):

enter image description here

Can anyone explain to my why this is the case? Intuitively I cannot see why it should be the case that the number of points in the rectange should increase, when switching to another $L_m$-distance?

The Manhatten distance $\geq$ Euclidean distance from what I can see in all instances, but why should this infer, an increase in points found in the $\delta$ x $2\delta$ space.

What am I missing?

$\endgroup$
  • 1
    $\begingroup$ I'm not sure what part you want to be explained. Your figure here shows that it is possible to fill the $\delta\times\delta$ square with 5 points of Manhattan distance at least $\delta$. Do you want to see why this isn't possible under the Euclidean distance? (and that therefore the maximum points per square is 4) Or do you want to know the number of points you can 'fit' in a square under other $L_m$ distances? $\endgroup$ – Discrete lizard Mar 29 at 16:30
  • $\begingroup$ @Discretelizard I do not understand why it is the case that there could be 5 points with manhattan distance, and only 4 points with euclidean distance. $\endgroup$ – NewDev90 Mar 29 at 18:18
  • $\begingroup$ I don't know how to answer "why" questions. You can see from the figure that the statement is true. I'm not sure what more there is to say. In what way is that not a sufficient explanation of why? Why do you get different numbers? Because they are different metrics. What more are you expecting? It's hard for me to tell what kind of answer you are hoping for, or what the concrete problem you are trying to solve is. Maybe if you can give us more context we'll be in a better position to help. And welcome to CS.SE! $\endgroup$ – D.W. Mar 29 at 18:27
1
$\begingroup$

One approach to see what is going on here is via the notion of an open ball under a given distance. Given a distance $d$, the open ball of radius $r$ around a point $p$ is given by $B_r(p):=\{q\mid d(p,q)<r\}$, i.e. the set of all points with distance less than $r$ to the center of the ball, $p$. In the plane and under the Euclidean distance, a ball is an open disk (a disk with the boundary removed) of radius $r$.

Since $\delta$ is the minimum distance between any pair of points in the left half, any pair of points in the left $\delta\times\delta$ square has a distance of at least $\delta$. This is equivalent to saying that the open ball of radius $r$ centered at a point $p\in P_L$ contains no other point $q\in P_L$. So, the maximum number of points from $P_L$ that can be in the $\delta\times \delta$ square is the largest number of points you can 'fit' into the square such that the ball surrounding each of those points contains no other point from $P_L$.

An open ball under the Euclidean distance is an open disk. If you place four points at the corners of the $\delta\times \delta$ square, the open disks of radius $\delta$ centered at those points together cover the entire square, so there is no position in the square to place for a fifth point.

However, under the Manhattan distance, an open ball of radius $\delta$ is an open square with diagonal length $\delta$, rotated by $45$ degrees (an "open diamond"). If we place such an open diamond at each corner of the $\delta\times \delta$ square, then there is exactly one position in the square not covered by an open diamond: the center of the square. This is the location where you can place a fifth point under the Manhattan distance.


As for the $L_m$-distance with $m>2$, note that the balls under these metrics all strictly contain the ball under the $L_2$-distance. I'll leave it up to you to use this fact to determine the maximum amount of points that can be in the $\delta\times\delta$-square.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This makes a lot of sense to me thanks. I think what I struggled with was the intuition of why it was the case, that there should be different amount of points in the $\delta \times \delta$ square. $\endgroup$ – NewDev90 Mar 30 at 6:56

Your Answer

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

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