O(n) algorithm for minimizing Manhattan distance between points 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.
 A: 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.
A: 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.
