[Cyan]<PreISLCedar>Stolfi>Papers>L1Neigh.tex!1

\abstract{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 $L1̌$ metric. By applying a suitable transformation to the input points, the same procedure can be used to compute the $L1̌$ 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 $L1̌$ metric. All three algorithms run in $O(n \lg n)$ total time and $O(n)$ space.}

{\it Closest-point problems} constitute an important area of computational geometry. A typical member of this class is the {\it all-nearest-neighbors problem}: for each point in a given set, determine which of the other points is closest to it. Another problem that can be included in this class is the computation of a {\it minimum spanning tree} (\mst) for a set of points, that is, a tree with those points as vertices, straight line segments as edges, and total edge length as small as possible.

The answer to those problems depends in general on the particular metric used to define distances and edge lengths; the Euclidean or $L2̌$ metric is perhaps the most common. In this paper we will be concerned almost exclusively with the {\it Manhattan} or $L1̌$ metric, in which the distance between two points $p$ and $q$ on the plane is by definition $\leftv px̌-qx̌\rightv + \leftv py̌-qy̌\rightv$.

Closest-point problems in the $L1̌$ metric have several applications. For example, Lee and Wong [\LeeWong] discuss various heuristics for scheduling head movements in handling I/O requests for secondary storage devices. These heuristics construct approximations to shortest traveling salesman tours in that metric. The minimum spanning tree problem in the $L1̌$ metric [\Hwang] has significant applications in wire routing on integrated circuits and printed circuit boards, where wires are often constrained to follow the ``Manhattan’’ geometry.

Efficient algorithms for Euclidean closest-point problems have been known for some time [\Shamos], but their extension to $L1̌$ and other metrics is generally not trivial. In the published literature all optimal algorithms for $L1̌$ closest-point problems are based on a common tool, the {\it Voronoi diagram in the $L1̌$ metric}. An $O(n\lg n)$ algorithm for constructing the $L1̌$ Voronoi diagram of $n$ points in the plane was given by Lee and Wong [\LeeWong], and later generalized by Lee [\Lee] to arbitrary $Lp̌$ metrics. The solution to several closest-point problems, including the {\mst} and all nearest-neighbor pairs, can be obtained from the Voronoi diagram within the same time bound.

A. Yao [\Yao] gave a different flavor of algorithm for computing minimum spanning trees in coordinate spaces, based on considering for each of the given points a sufficient number of closest neighbors in different directions. However, for the planar case Yao’s algorithm runs in time $O(n↑{2-1/8} (\lg n)↑{1-1/8})$, which is not as good as the bounds given above. In this note we show that Yao’s ideas admit of a very simple implementation for the plane\foot\dag{In the $L1̌$ metric. Unless explicitly stated otherwise, this qualification applies also to all distances and lengths referred to or implied in the rest of the paper.}. The resulting {\mst} algorithm avoids the overhead of constructing the Voronoi diagram, but still runs in time $O(n \lg n)$, and is therefore optimal.

In our method we first show how to compute in time $O(n \lg n)$ the nearest north-east (NE), or first quadrant, neighbor for each point in the given collection. We then modify this technique to give the nearest neighbor in each octant, and establish that the set of edges from each point to its eight nearest neighbors, one in each octant, encompasses an {\mst}.

As a final remark, we note that our algorithm also solves the {\mst} problem in the {\it $L\̌infty$ metric}, defined by $d\̌infty(p,q) =\max\set{\leftv px̌-qx̌\rightv, \leftv py̌-qy̌\rightv}$, since a rotation by $45\deg$ and a scaling by a factor of $1/\sqrt{2}$ transforms $L\̌infty$ distances into $L1̌$ distances.

In this section we discuss the following problem, which is of interest in its own right. Let $n$ points in the plane be given. We wish to compute, for each of the given points $p$, its {\it nearest north-east neighbor}. By that we mean the point in our collection which is in the first quadrant with respect to $p$, and closest to $p$. (Two fine points: if more than one nearest neighbor to $p$ exists, we choose one arbitrarily. We also adopt some suitable convention to indicate the case where no point exists at all in the first quadrant of $p$.)

Using this lemma, we now devise a divide-and-conquer strategy for our problem: Start out by sorting all points in $x$. (This step is not strictly necessary, as we can use a linear median finding algorithm, but it would be the implementation of choice in practice.) We describe a recursive procedure that not only computes all NE nearest neighbors, but also returns the points sorted in $y$. We first find an $x$ value that divides our points into the left and right halves, and recursively call our procedure on the two halves. The computed NE neighbors for points on the right half are already the correct NE neighbors for the full problem. The key question is how fast we can update the NE neighbors of points on the left half.

We will show that in $O(n)$ time we can compute for each point on the left half its nearest NE neighbor among the points on the right half. Thus the NE neighbors of the left half points can be updated and the computation completed in $O(n)$ time. (This includes merging the two $y$-sorted lists of the left and right points into a common sorted list.) By standard analysis of algorithm techniques it follows that the overall computation time will then be $O(n \lg n)$.

To accomplish the computation described above we will keep three pointers. One pointer, {\it left}, will advance down the sorted list of left half points in decreasing $y$. And the other two, {\it right} and {\it min}, will advance down the list of the right hand points in decreasing $y$. No pointer will ever back up. See fig. 2. In the normal case we are seeking the nearest NE neighbor of the left hand point indicated by {\it left}. Pointer {\it right} is advancing downwards on the list of right hand points, while always staying at points with $y$ coordinates larger than that of {\it left}. Pointer {\it min} is keeping track of the nearest right hand element to {\it left} seen so far. As {\it right} advances to the next element, one of three things can happen. (1) The point that {\it right} points to is higher in $y$ than {\it left}, but further away than {\it min}: in this case we do nothing. (2) The point that {\it right} points to is higher in $y$ than {\it left}, but closer than {\it min}: in this case we set {\it min} equal to {\it right}. (3) The point that {\it right} points to drops below {\it left}: in this case we output {\it min} as the nearest NE neighbor of {\it left} (among the right points), and advance {\it left}. Lemma 1 proves that this iteration correctly computes the nearest NE neighbor of each point on the left among points on the right. Since no pointer ever backs up, the linearity of this pass is immediate.

For the {\mst} algorithm in section 3 we will actually need to find the first octant nearest neighbor of each point in our set. This can be done by using the above algorithm after appropriately tranforming our set of points. Consider the linear transformation $T$ of the plane defined by $T:\ (x,y) \mapsto ((x-y)/2,y)$. It is simple to check that point $q$ is in the first octant of point $p$ if and only if $Tq$ is in the first quadrant of $Tp$. Intuitively, $T$ is a shearing transform parallel to the $x$ axis taking octants into quadrants. Furthermore, if $q1̌$ and $q2̌$ are two points in the first octant of $p$ and $d(p,q1̌) d(p,q2̌)$, then $d(Tp,Tq1̌) d(Tp,Tq2̌)$, and conversely. This is because $px̌+py̌ = 2(Tpx̌+Tpy̌)$, i.e., $T$ maps lines of slope $-1$ to lines of slope $-1$. Thus nearest first octant neighbors map to nearest first quadrant neighbors under $T$. Slightly modified linear transformations can be used to map any other octant onto the first quadrant.

There exist several minimum spanning tree algorithms for graphs that require no more than $O(n \lg n)$ time when the given graph contains no more than $O(n)$ edges. Kruskal’s algorithm [\Krusk], implemented with an appropriate union-find data structure, gives this bound. See also the extensive discussion in Cheriton and Tarjan [\ChTar]. The lemma below asserts that there exists an especially simple set of edges for our $n$ points that is linear in size and contains some {\mst}.

\lemma{2}{Let $n$ points in the plane be given. Consider the graph $G$ obtained by joining every point to each of its eight nearest neighbors, one in each octant, by an edge whose weight is the $L1̌$ distance between the two {\rm (see fig. 3)}. Then an {\mst} for $G$ is also an {\mst} for our point set in the $L1̌$ metric.}

\proof{We will show that the edges of some {\mst} for our set of points are contained among the edges of $G$. We adopt the convention that each octant contains the half-axis bounding it and shared with the clockwise following octant. The value of choosing octants is that if $v$ and $w$ are two nearest neighbors of point $u$ in the same octant, then $d(v,w) < d(u,v) = d(u,w)$.

\pp Consider an edge $e$ from point $u$ to point $v$ in some {\mst} of the set of points. We can assume, without loss of generality, that $v$ is in the first octant of $u$. We now claim that $v$ is a NE nearest neighbor of $u$. See fig. 4. For suppose there could be some point $w$ in the first octant of $u$, strictly closer to it than $v$. If we remove the edge $e$ from the {\mst}, we will disconnect it into two fragments, one of which must contain $w$. Now note that $d(u,v) > d(u,w)$, and also $d(u,v) > d(v,w)$, since $u$ is farther away from $v$ than any other point in the shaded area. By joining $w$ to either $u$ or $v$, according to which of them lies in the fragment not containing $w$, we obtain a new and smaller {\mst}, which is a contradiction.

\pp If the nearest neighbor of $u$ we chose to include in $G$ was not $v$, but (say) $x$, where $xv$, then consider again deleting $e$ from our {\mst}. The fragment in which $x$ falls must contain $v$, else adding the edge $(v,x)$ would result in a smaller {\mst}, by the observation of the previous paragraph. Thus edge $(u,x)$ can be used instead of $e$ to obtain an equivalent {\mst}.}

As a result of lemma 2 we have a new {\mst} algorithm that works in time $O(n \lg n)$. We invoke the method of section 2 eight times to compute the eight nearest octant neighbors of each point. (Actually these computations can be merged into four pairs of two diametrically opposite octants each, since the transformation $T$ that maps the first octant to the first quadrant also maps the fifth octant to the third quadrant, etc.) We then throw all the edges thus produced into Kruskal’s algorithm, and obtain our {\mst}.

We have shown how to compute all NE nearest neighbors of $n$ points in the plane in the $L1̌$ metric in time $O(n \lg n)$. This has also given us an algorithm for computing the {\mst} of the $n$ points within the same time bound. It would be of interest to explore whether these ideas extend to higher dimensions.