1
$\begingroup$

Given two sets points with each point either "Black" or "White", design an algorithm to find the pair of points, one that is black and another that is white, such that the Manhattan distance between them is minimized. Note that we can assume that all coordinates are distinct.

There is one assumption - we are given f and g: all black points are in region {(x, y)|x ≥ f, y ≥ g} and all white points are in {(x, y)|x ≤ f, y ≤ g}.

Question: Considering the assumption, Is there an O(n) algorithm to compute the pair?

My attempt:

So far, I have looked at this problem and visualized it as much as possible but can't find a way to get it into O(n).

I did have one promising thought: find the point closest to (f,g) that is black. And then find the point closest to (f,g) that is white. Those two points should correspond to the pairs; and would run in O(n). This is just a guess though.

Any tips, pointers, or ideas would be greatly appreciated.

$\endgroup$
  • 1
    $\begingroup$ Thanks hardmath! I updated the title. $\endgroup$ – user143059 Oct 21 '14 at 0:51
  • $\begingroup$ I believe my logic is correct - but this is just a hard guess. I can't think of anything else. $\endgroup$ – user143059 Oct 21 '14 at 0:54
  • $\begingroup$ I like your guess a lot. Why not assume the black and white points as described (closest to (f,g)) and see if having a pair of points closer to each other gives a contradiction. $\endgroup$ – hardmath Oct 21 '14 at 0:55
  • $\begingroup$ Hmm - I've been drawing it out - and I suppose when there are multiple "Black" or "White" points that minimize the distance between (f,g), we could have an issue.. $\endgroup$ – user143059 Oct 21 '14 at 1:04
  • 1
    $\begingroup$ There's a bit of "geometry" that goes with the Manhatten distance, which is that if a point in the "white" quadrant has a distance $D$ to a point in the "black" quadrant, that distance can be attained by a "jagged line path" that passes through (f,g). $\endgroup$ – hardmath Oct 21 '14 at 1:43
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Perhaps a few more words about the OP's idea of locating points, both Black and White, closest to (f,g). The issue is not so much a triangle inequality as an equality of sums of distances imposed by the geometry specific to this problem.

Consider any Black point (f+a,g+b) and any White point (f-c,g-d) in their respective quadrants, a,b,c,d ≥ 0.

Now the Manhattan distance between these points is a+c+b+d, and we note that this is the sum of distances from each point to the crux point (f,g). It follows that minimizing the distance between a pair of points, one in each quadrant, amounts to finding a point closest to (f,g) in each quadrant.

Of course there is no uniqueness of the pair of points guaranteed by this; one or both quadrants might have multiple points that attain the minimum distance to (f,g). However the minimum distance itself is unique and may be determined in linear time by separately scanning both quadrants to locate their closest point to (f,g) as Adriano has outlined with a code snippet.

$\endgroup$
  • $\begingroup$ Thanks a lot hardmath! This makes things a lot more clear! $\endgroup$ – user143059 Oct 21 '14 at 3:36

Your Answer

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