On computing all north-east nearest neighbors in the L1 metric

Given a collection of n points in the plane, we exhibit an algorithm that computes the nearest neighbor in the north-east (first quadrant) of each point, in the L₁ metric. By applying a suitable transformation to the input points, the same procedure can be used to compute the L₁ nearest neighbor in any given octant of each point. This is the basis of an algorithm for computing the minimum spanning tree of the n points in the L₁ metric. All three algorithms run in O(n lg n) total time and O(n) space.