I'm trying to understand the closest pair of points problem. I am beginning to understand the two-dimensional case from a question a user posted some years ago. I'll link it in case someone wants to look at it: For 2-D case (plane) - "Closest pair of points" algorithm.
What I'm trying to do is: Given two points $p_1$ and $p_2$ in the plane, the $L_\infty$-distance between them is given by max$(|x_1, x_2|, |y_1,y_2|)$. Modify the closest-pair algorithm to use the $L_\infty$ distance.
From what I understand (thinking about two points in an xy plane) the Euclidean distance would be the line that directly connects the two points. To see what the L-infinity distance looks like, draw a rectangle with the two points at two opposite corners. The L-infinity distance would then be the length of the longest side of the rectangle.
The only difference is in the "merging" part of the recursion. Let the two sets created by the dividing line be called as $L$ and $R$, respectively (for left and right sets). Via recursion, we have our temporary current closest pair -- let's say its at distance $M$. Similar to the original algorithm, we filter only the points that is within $M$ distance from the dividing line, sort the points by their $y$ coordinates, and sweep the points from top to bottom. For each point $(x', y')$ in $L$, consider the square of size $2M \times 2M$ centered at this point. How many points in $R$ within $M$ distance from the dividing line can be inside this square at most? $6$ points (I'm being ultra conservative here), and those corresponds to the points in $R$ whose $y$ coordinate is between $y' - M'$ and $y' + M$. Thus, a similar reasoning holds as in the original algorithm here.