## CLRS closest-pair $L_m$ distances

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): 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?

Posted on Categories proxies