[Math] Modify the closest-pair algorithm to use the $L_\infty$ distance.

algorithmscomputational geometry

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.

Best Answer

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.

Related Solutions

[Math] closest pair in N-Dimensional

The closest pair was either already found, or is in the 2-d-thick slab which can only include a low number of points. No need to reduce the dimension, just apply the algorithm recursively left, right and on the slab (cycling the direction the separating hyperplane is perpendicular to), optimality is implicit. Here are other slides.

[Math] O(n) algorithm for minimizing Manhattan distance between points

Your guess is indeed correct! If you're interested in proving correctness, use a proof by contradiction and apply the triangle inequality.

Now let's come up with an algorithm that will find the black point $(x_0, y_0)$ in the unordered set $B$ of all black points such that $(x_0, y_0)$ is closest to $(f,g)$. This is basically a linear search. In pseudocode (Python), we can do something like:

def findClosestBlack(f, g, B):
    # Initialize our closest point to be furthest possible, at (+inf, +inf).
    (x0, y0) = (float("inf"), float("inf"))

    # For each point in B, check if its Manhattan distance away from (f, g) is
    # closer than that of (x0, y0). If we find a closer point, then update.
    for (x, y) in B:
        if abs(x - f) + abs(y - g) < abs(x0 - f) + (y0 - g):
            (x0, y0) = (x, y)

    return (x0, y0)

Use a similar function to find the closest white point. Then since all $n$ points are scanned exactly once, the total running time will be $O(n)$, as desired.

Best Answer

Related Solutions

[Math] closest pair in N-Dimensional

[Math] O(n) algorithm for minimizing Manhattan distance between points

Related Question