An Optimal Algorithm for the Angle-Restricted All Nearest Neighbor Problem on the Reconfigurable Mesh, with Applications.
AbstractGiven a set S of n points in the plane and two directions $r_1$ and $r_2,$ the Angle-Restricted All Nearest Neighbor problem (ARANN, for short) asks to compute, for every point p in S, the nearest point in S lying in the planar region bounded by two rays in the directions $r_1$ and $r_2$ emanating from p. The ARANN problem generalizes the well-known ANN problem and finds applications to pattern recognition, image processing, and computational morphology. Our main contribution is to present an algorithm that solves an instance of size n of the ARANN problem in O(1) time on a reconfigurable mesh of size nn. Our algorithm is optimal in the sense that $\Omega\;(n^2)$ processors are necessary to solve the ARANN problem in O(1) time. By using our ARANN algorithm, we can provide O(1) time solutions to the tasks of constructing the Geographic Neighborhood Graph and the Relative Neighborhood Graph of n points in the plane on a reconfigurable mesh of size nn. We also show that, on a somewhat stronger reconfigurable mesh of size $n\times n^2,$ the Euclidean Minimum Spanning Tree of n points can be computed in O(1) time.
Introduction
Recently, in an effort to enhance both its power and flexibility, the mesh-connected architecture
has been endowed with various reconfigurable features. Examples include the bus
automaton [21, 22], the reconfigurable mesh [15], the mesh with bypass capability [8], the
content addressable array processor [29], the reconfigurable network [2], the polymorphic processor
array [13, 14], the reconfigurable bus with shift switching [11], the gated-connection
network [23, 24], and the polymorphic torus [9, 10]. Among these, the reconfigurable mesh
has emerged as a very attractive and versatile architecture.
In essence, a reconfigurable mesh (RM) consists of a mesh augmented by the addition
of a dynamic bus system whose configuration changes in response to computational and
communication needs. More precisely, a RM of size n \Theta m consists of nm identical SIMD
processors positioned on a rectangular array with n rows and m columns. As usual, it is
assumed that every processor knows its own coordinates within the mesh: we let P (i;
denote the processor placed in row i and column j, with P (1; 1) in the north-west corner of
the mesh.
Each processor P (i; j) is connected to its four neighbors P (i \Gamma
and P exist, and has 4 ports denoted by N, S, E, and W in Figure 1.
Local connections between these ports can be established, under program control, creating
a powerful bus system that changes dynamically to accommodate various computational
needs. We assume that the setting of local connection is destructive in the sense that setting
a new pattern of connections destroys the previous one.
Most of the results in this paper assume a model that allows at most two connections
to be set in each processor at any one time. Furthermore, these two connections must
involve disjoint pairs of ports as illustrated in Figure 2. Some other models proposed in
the literature allow more than two connections to be set in every processor [9, 10]. One of
our results uses such a model. In accord with other workers [9, 10, 13-16, 21] we assume
that communications along buses take O(1) time. Although inexact, recent experiments
with the YUPPIE and the GCN reconfigurable multiprocessor system [16, 23, 24] seem to
indicate that this is a reasonable working hypothesis. It is worth mentioning that at least

Figure

1: A reconfigurable mesh of size 4 \Theta 5

Figure

2: Examples of allowed connections and corresponding buses
two VLSI implementations have been performed to demonstrate the feasibility and benefits
of the two-dimensional reconfigurable mesh: one is the YUPPIE (Yorktown Ultra-Parallel
Polymorphic Image Engine) chip [9, 10, 16] and the other is the GCN (Gated-Connection
Network) chip [23, 24]. These two implementations suggested that the broadcast delay,
although not constant, is very small. For example, only 16 machine cycles are required to
broadcast on a 10 6 -processor YUPPIE. The GCN has further shortened the delay by adopting
pre-charged circuits. Newer developments seem to suggest the feasibility of implementations
involving the emerging optical technology.
One of the fundamental features that contributes to a perceptionally relevant description
useful in shape analysis is the distance properties among points in a planar set. In
this context, nearest- and furthest-neighbor computations are central to pattern recognition
classification techniques, image processing, computer graphics, and computational morphology
[4, 20, 26, 27]. In image processing, for example, proximity is a simple and important
metric for potential similarities of objects in the image space. In pattern recognition, the
same concept appears in clustering, and computing similarities between sets [4]. In mor-
phology, closeness is often a valuable tool in devising efficient algorithms for a number of
seemingly unrelated problems [26].
A classic problem in this domain involves computing for every point in a given set S, a
point that is closest to it: this problem is known as the All-Nearest Neighbor problem (ANN,
for short) and has been well studied in both sequential and parallel [1, 4, 20, 26]. Recently,
Jang and Prasanna [5] provided an O(1) time algorithm for solving the ANN problem for n
points in the plane on a RM of size n \Theta n.
In this paper we address a generalization of the ANN problem, namely the the Angle-
Restricted All Nearest Neighbor problem (ARANN, for short). Just as the ANN problem,
the ARANN problem has wide-ranging applications in pattern recognition, image processing,
and morphology.
For points p and q in the plane, we let d(p; q) stand for the Euclidean distance between
p and q. Further, we say that q is (r )-dominated by p if q lies inside of the closed planar
region determined by two rays in directions r 1 and r 2 emanating from p. In this terminology,
a point q in S is said to be the (r )-nearest neighbor of p if q is (r )-dominated by p
and )-dominated by pg. The ARANN problem
involves determining the (r )-nearest neighbor of every point in S.
Refer to Figure 3 for an illustration. Here, p 2 is (0; -=3)-dominated by p 1 , but is not (0; -=3)-
dominated by p 4 . The (0; -=3)-nearest neighbor of p 1 is p 2 .
A class of related problems in pattern recognition and morphology involves associating
a certain graph with the set S. This graph is, of course, application-specific. For example,
in pattern recognition one is interested in the Euclidean Minimum Spanning Tree of S, the
Relative Neighborhood Graph of S, the Geographic Neighborhood Graph, the Symmetric
Furthest Neighbor Graph, the Gabriel Graph of S, and the Delaunay Graph of S, to name
a few [20, 25-27].
The Euclidean Minimum Spanning Tree of S, denoted by EMST(S), is the minimum

Figure

3: Illustrating (0; -)-domination and the corresponding ARANN graph

Figure

4: Lune of p and q
spanning tree of the weighted graph with vertices S and with the edges weighted by the
corresponding Euclidean distance. In other words, the edge-set is
Sg where (p; q; d(p; q)) is the edge connecting points p and q having weight d(p; q).
The Relative Neighborhood Graph, RNG(S) of a set S of points in the plane has been
introduced by Toussaint [26] in an effort to capture many perceptually relevant features of
the set S. Specifically, given a set S of points in the plane, RNG(S) has for vertices the points
of S together with an edge between p and q whenever d(p; q) - max s2S fd(p; s),d(q; s)g. An
equivalent definition states that two vertices p, q are joined by an edge in RNG(S) if no
other points of S lie inside LUNE(p; q), the lune of p, q defined as the set of points in the
GNG

Figure

5: Illustrating EMST, RNG, GNG, and GNG 1
plane enclosed in the region determined by two disks with radius d(p; q) centered at p and
q, respectively. Refer to Figure 4 for an illustration.
be the undirected graph with vertex-set S and with edge-set
f(p; q)jq is the i-=3)-nearest neighbor of pg. The GNG of S, denoted GNG(S),
is the graph with vertex-set S and whose edges are [ 1-i-6 E i . Refer to Figure 5 for an
example of the concepts defined above.
Given set S of n points in the plane and two directions r 1 and r 2 , the Angle-Restricted
All Nearest Neighbor graph of S, denoted ARANN(S) is the directed graph whose vertices
are the points in S; the points p and q are linked by a directed edge from p to q whenever
q is the (r )-nearest neighbor of p. The reader will not fail to note that the problem of
computing the (r )-closest neighbor of each point in S and the problem of computing the
graph ARANN(S) of S are intimately related, in the sense that the solution to either of
them immediately yields a solution to the other. For this reason in the remaining part of
this work we shall focus on the problem of computing the graph ARANN(S) and we shall
refer to this task, informally, as solving the ARANN problem.
Referring again to Figure 3, the corresponding ARANN graph contains the directed edges
is the (0; -)-closest neighbor of p 1 and p 3 is the (0; -)-closest
neighbor of p 2 . The points p 3 and p 4 have no (0; -)-closest neighbor and so, in the ARANN
graph they show up as isolated vertices.
Several sequential algorithms for the computing the EMST, the GNG, the ARANN, and
the RNS graphs of a set of points have been proposed in the literature [3, 7, 25, 26]. In
particular, [3] has shown that the ARANN graph of a set of n points in the plane can be
computed sequentially in O(n log n) time.
The main contribution of this work is to present an algorithm to compute the ARANN
graph of n points in O(1) time on a RM of size n \Theta n. We also show that our algorithm is
optimal in the sense that n 2 processors are necessary to compute the ARANN of n points in
O(1) time. It is not hard to see that the ANN problem is easier than the ARANN, because
the ANN corresponds to the computation of ARANN for the particular directions 0 and 2-.
Our second main contribution is to extend our ARANN algorithm to solve in O(1) time the
problems of computing the Geographic Neighborhood Graph, the Relative Neighborhood
Graph, and the Euclidean Minimum Spanning Tree of a set S of n points in the plane.
As we already mentioned, Jang and Prasanna [5] have shown that the All Nearest Neighbor
problem, of a set S of n points in the plane, can be solved in O(1) time on a RM of size
n \Theta n. The key idea of the algorithm in [5] is as follows: In the first stage, the points are
partitioned into n 1=4 horizontal groups each of n 3=4 points by n 1=4 \Gamma 1 horizontal lines and
into n 1=4 vertical groups of n 3=4 points by n vertical lines. For each point, the nearest
neighbor over the all points that are in the same horizontal or vertical group is retained as
a candidate for the nearest neighbor over the whole set of points. Having computed the set
of candidates, the second stage of the algorithm in [5] uses the fact that the candidates of at
most 8
n points are not the correct nearest neighbors over all the points. So, by computing
the nearest neighbor of these exceptional 8
n points, the ANN problem can be solved. If the
angle is restricted, then this algorithm does not work, because it is possible that none of the
candidates retained in stage 1 is the actual angle restricted nearest neighbor. This situation
is depicted in Figure 6. We will develop new tools for dealing with the ARANN problem.
These tools are interesting in their own right and may be of import in the resolution of other
related problems.
At the same time, it is clear that by using the ARANN algorithm, the ANN problem and
the task of computing the GNG can be solved in O(1) time on an n \Theta n RM. Furthermore, the
RNG can be computed in O(1) time on an n \Theta n RM and the EMST can be computed in O(1)
time on an n \Theta n 2 RM. These algorithms are based on the fact that the RNG is a subgraph of
GNG and EMST is a subgraph of RNG [25,26]. In Section 2 we demonstrate a lower bound
on the size of a reconfigurable mesh necessary to compute the ARANN, GNG, RNG, and

Figure

None of the candidates of stage 1 are the true (0; -)-nearest neighbors
EMST in O(1) time. Section 3 presents basic algorithms used by our ARANN algorithm.
Section 4 presents our optimal ARANN algorithm and Section 5 presents algorithms for
the GNG, RNG, and EMST. Finally, Section 6 offers concluding remarks and poses open
problems.
Let us consider the ARANN problem for the directions \Gamma-=2 and -=2. Consider a set
of points on the x-axis such that point (a
is assigned to the i-th column of an RM of size m \Theta n. After the computation of the ARANN,
the processors of the i-th column know the (\Gamma-=2; -=2)-nearest neighbor of (a
that a 1 ! a n=2 ! a for each point
-=2)-nearest neighbor is the point (a i+n=2 ; 0). Therefore,
information about n=2 points (a n=2 ; 0); (a n=2+1 must be transferred through
the m links that connect the (n=2 \Gamma 1)-th column and the n=2-th column of the RM. Hence,
time is required to solve the ARANN problem. Therefore, we have the following
result.
Theorem 2.1
processors are necessary to solve an instance of size n of the ARANN
problem on the RM in O(1) time.
Since the proof above can be applied to the GNG, RNG, and EMST, we have
Corollary 2.2
processors are necessary to compute the GNG, RNG, and the EMST
of n points in O(1) time on a RM.
3 Basic Algorithms
This section reviews basic computational results on reconfigurable meshes that will be used
in our subsequent algorithms. Recently, Lin et al. [12], Ben-Asher et al. [2], Jang and
Prasanna [6], and Nigam and Sahni [17] have proved variants of the following result.
Lemma 3.1 A set of n items stored one per processor in one row or one column of a
reconfigurable mesh of size n \Theta n can be sorted in O(1) time.
For a sequence of n numbers, its prefix-maxima is a sequence
gg. The prefix-minima can be defined
in the same way. For the prefix-maxima and prefix-minima, we have
Lemma 3.2 Given a sequence of n numbers stored one per processor in one row of a reconfigurable
mesh of size n \Theta n ffl , its prefix-maxima (resp. prefix-minima) can be computed in
time for every fixed ffl ? 0.
Proof. Olariu et al. [18] have shown to compute the maximum of n items in O(1) time on
reconfigurable mesh of size n \Theta n. Essentially, if we assign n processors to each number, we
can determine if there is a number larger than it. If such a number is not found, it is the
maximum. Since an n \Theta n RM can find the maximum of n elements in O(1) time, an easy
extension shows that an n \Theta n 2 RM can compute the prefix-maxima of n numbers in O(1)
time.
Based on this idea, we can devise an O(1) time algorithm for an n \Theta n ffl RM. Assume that
each number is assigned to a row of the platform. Partition the sequence
of n numbers into n ffl=2 sequences A 1 ; A ffl=2 each of which contains n 1\Gammaffl=2 numbers.
Next, compute the (local) prefix-maxima of each A i (1 - i - n ffl=2 ) on an n 1\Gammaffl=2 \Theta n ffl submesh
recursively. Let be the maximum within A i . Further, compute the (global) prefix-
maxima of a sequence )g. This can be done in O(1) time
by the O(1) time algorithm discussed above. Finally, for each number a j (2 A i ), compute the
maximum of its local prefix-maximum and the global prefix-maximum maxfA
that corresponds to the prefix-maximum of a j . Since the depth of the recursion is O(1=ffl),
the maximum can be computed in O(1) time. 2
The prefix-sums of n binary values can be computed in a similar fashion. The reader is
referred to [19] for the details.
Lemma 3.3 For every fixed ffl ? 0, the prefix-sums
of a binary sequence can be computed in O(1) time on a
reconfigurable mesh of size n \Theta n ffl .
Our next result assumes a reconfigurable mesh wherein a processor can connect, or fuse,
an arbitrary number of ports [28]. On this platform, we will show basic graph algorithms that
are essentially the same as those previously presented [28]. However, the number of processors
is reduced by careful implementation of the algorithms to the RM. A graph E)
consists of a set V of n vertices and an edge-set
e edges where u E) is said to be numbered if the
vertex set is ng. A graph E) is weighted if the edge-set is
positive number. The reachability
problem [28] for a vertex u of G involves determining all the vertices of G that can be reached
by a path from u. Here, u is referred to as the source.
Lemma 3.4 Given a numbered graph E) and a node u 2 V , the single source
reachability problem can be solved in O(1) time on an n \Theta e RM, if each edge is assigned to
a column of the RM.
Proof. Let n), be the edge assigned to the i-th column of a RM of
size n \Theta e. For each i, P connect their four ports into one. All the other

Figure

7: Bus configuration for the reachability problem
processors connect their E and W ports as well as their N and S ports in pairs.
We note that the bus configuration thus obtained corresponds to the graph in the sense
that the horizontal buses in row u i and row v i row are connected through the vertical bus in
column i, as illustrated in Figure 7.
Next, processor P (u; 1) sends a signal from its E port and every processor P (v; 1) reads
its E port. It is not hard to see that vertex v is reachable from u if and only if processor
(v; 1) has received the signal sent by P (u; 1). Therefore, the reachability problem can be
solved in O(1) time on an n \Theta e reconfigurable mesh that allows all ports to be fused together.By using the single source reachability algorithm, we have the following lemma.
Lemma 3.5 Given a numbered weighted graph G with n vertices and e edges, its Minimum
Spanning Tree can be computed in O(1) time on a reconfigurable mesh of size e \Theta ne provided
that every processor can fuse all its ports together.
Proof. For each i, (1 - i - e), let G be the graph such that
lexicographically larger
than (w for each i, it is determined whether u i and v i are reachable in the graph
G i . If so, then not an edge of MST, otherwise it is an MST edge. By Lemma
3.4 the reachability can be determined in O(1) time on an e \Theta n RM, so the MST edges can
be determined in O(1) time on an e \Theta ne RM, as claimed. 2
4 An Optimal Algorithm for the ARANN Problem
Consider a collection S of n points in the plane and directions r 1 and r 2 with
2-. The main goal of this section is to present an optimal O(1) time algorithm for computing
the corresponding graph ARANN(S).
We begin our discussion by pointing out a trivial suboptimal solution to the problem at
hand.
Lemma 4.1 For every fixed ffl ? 0, the task of solving an arbitrary instance of size n of the
ARANN problem can be performed in O(1) time on a RM of size n \Theta n 1+ffl .
Proof. Partition the RM into n submeshes of size n \Theta n ffl and assign each submesh to a
point. Each point p find, in its own submesh, the nearest neighbor q over all the points
)-dominated by p, and report the edge (p; q) as an edge of ARANN(S). We note that
the task of finding the nearest neighbor of every point in S can be seen as an instance of the
(prefix) minimum problem and can be solved in O(1) time by the algorithm of Lemma 3.2. 2
In the remainder of this section we will show how to improve this naive algorithm to
run in O(1)-time on a RM of size n \Theta n. First, assume that the given directions are 0
and r, with that is, the angle of the closed region is acute. Consider a set
of points in the plane stored one per processor in the first row of a RM
of size n \Theta n such that for all i, (1 - i - n), processor P (1; i) stores point p i . The details of
our algorithm are spelled out as follows.
Step 1. Sort the points in S by y-coordinate and partition them into n 1=3 subsets Y
of n 2=3 points each, such that the y-coordinate of all points in Y i is smaller than the
y-coordinate of all points in Y
Step 2. For each point p in S compute x 0 and sort the points by
are x- and y-coordinate of p. Next, partition the points into

Figure

8: Partitioning into X's and Y 's
subsets points each, such that for every choice of points p in
Step 3. For each point p in X i , r)-nearest neighbor X(p) over all
points in X
Step 4. For each point p in Y i , r)-nearest neighbor Y (p) over all
points in Y
Step 5. For each i and j, (1 - For each point
its (0; r)-nearest neighbor Z(p) over all points in Z i;j ;
Step 6. For each point p, find the closest of the three points X(p), Y (p), and Z(p), and
return it as the (0; r)-nearest neighbor of p.
We refer the reader to Figure 8 for an example, where
(Actually, 4, but this inconsistency is nonessential.)
Our next goal is to show that the algorithm we just presented can be implemented to
run in O(1) time on a RM of size n \Theta n. By virtue of Lemma 3.1, Steps 1 and 2 can be
completed in O(1) time on a RM of size n \Theta n. In Step 3, a submesh of size n \Theta n 2=3 can
Minima(P )-=3

Figure

9: Illustrating Maxima(S) and Minima(S) for directions 0 and -=3
be assigned to each X i . Consequently, Step 3 can be completed in O(1) time by the naive
algorithm of Lemma 4.1. In the same way, Step 4 can be implemented to run in O(1) time.
Step 6 involves only local computation and can be performed, in the obvious way, in O(1)
time.
The remainder of this section is devoted to showing that with a careful implementation
Step 5 will run in O(1) time. We shall begin by presenting a few technical results that are
key in understanding why our implementation works.
Consider, as before, a set of points. A point p i in S is a (0; r)-maximal
(resp. minimal) point of S if p i is not (0; r)-dominated by (resp. does not (0; r)-dominate)
any other point in S. We shall use Maxima(S) (resp. Minima(S)) to denote the chain of
all maximal points in S specified in counter-clockwise order (resp. all minimal points in
clockwise order). These concepts are illustrated in Figure 9 for the directions 0 and -=3.
Next, we propose to show that only points in Maxima(X may have their (0; r)-
nearest neighbor in Z i;j . Moreover, if the (0; r)-nearest neighbor of a point in Maxima(X i "Y j )
lies in Z i;j , then it can only be in Minima(Z i;j ).
Lemma 4.2 For three points direction r (0
Proof. Consider the triangle let u be the point where the edge 3 of this
triangle cuts one of the rays in the directions 0 or r emanating from p 2 . We shall assume,
without loss of generality, that the point u lies on the ray in the direction 0.
must be larger than
-=2. This implies that that the angle (which is larger that the angle
larger than -=2. Hence,
Note that Lemma 4.2 does not hold for a direction r larger than -=2. This is the reason we
restricted the angle r to be less than -=2.
Consider two sets of points P and Q such that all points in P (0; r)-dominate all the
points in Q. Let ARANN r (P; Q) be a set of edges (p; q) such that p belongs to P , q belongs
to Q, and q is the (0; r)-nearest neighbor of p. We have the following lemma.
4.3 No two edges in ARANN r (P; Q) intersect.
Proof. Suppose not: some two edges (p; q) and (p intersect at a
point u. ?From the triangle inequality applied to the triangles puq 0 and p 0 uq we have
But now, (1) implies that either must hold. However,
this contradicts the assumption that both (p; q) and (p are edges in ARANN r
Hence, the graph ARANN r (P; Q) is planar.
Lemma 4.4 If (p;
Proof. If p does not belong to Minima(P ), then there exists a point p 0 in Minima(P ) that
dominates q. But now, Lemma 4.2 guarantees that a contradiction. In
case q does not belong to Maxima(Q) we can show a contradiction in an essentially similar
fashion. 2
Lemma 4.4 has the following important consequence.
Corollary 4.5 ARANN r
Corollary 4.5 guarantees that in order to compute ARANN r (P; Q) examining all the
pairs of points p in P and q in Q is not necessary: all that is needed is to compute
ARANN r (Minima(P ); Maxima(Q)).
To pursue this idea further, write Minima(P
and assume that for some fixed ffl, (0
motivates the following approach to compute ARANN r (Minima(P ); Maxima(Q)).
Let sample(Minima(P )) be a subset of n ffl=2 points fp n ffl=2 of Minima(P )
and partition Minima(P ) into n ffl=2 chains in such a way that
and
ffl for every k, g.
Refer to Figure 10 for an illustration. For each k (1
(2 Q) be the
(0; r)-nearest neighbor of p kn ffl=2 over all Q.
Observe that the points q j k
thus defined induce a partition of the set Q into n ffl=2 chains
ffl=2 such that
and
ffl for every k,
g.
We note that q j k
4.3 guarantees that in order to compute the (0; r)-
nearest neighbor of a point p in P k with respect to Maxima(Q), we can restrict ourselves
to computing the (0; r)-nearest neighbor of p over Q k . In other words, ARANN r
ARANN r (P k ; Maxima(Q)). Therefore, the task of computing ARANN r (Minima(P ); Maxima(Q))
reduces to that of computing ARANN r
The sampling strategy outlined above leads to the following algorithm for computing
ARANN r (Minima(P ); Maxima(Q)) in O(1) time on a RM of size n \Theta n ffl , for some fixed
We assume that each point in Minima(P ) has been assigned to one column and
each point in Maxima(Q) has been assigned to one row of the RM.
Partition columnwise the original RM of size n \Theta n ffl into n ffl=2 submeshes of size
n \Theta n ffl=2 each. In the k-th such submesh, 1 - k - n ffl=2 , compute d(p kn ffl=2 ; q) for all
points q in Maxima(Q);
Step 2 For every k, (1 - k - n ffl=2 ), use the k-th submesh to compute

Figure

10: Partitioning Minima(P ) and Maxima(Q)
ffl the (0; r)-nearest neighbor q j k
of p kn ffl=2
by finding the smallest of the distances
computed above;
ffl using the point q
determine Q k .
If then the (0; r)-nearest neighbor of every point p in P k is precisely q j k
, and
thus
We shall, therefore, assume that jQ k j - 2
for all k;
Step 3 Partition the given RM of size n\Thetan ffl rowwise into n ffl=2 submeshes as follows. For each
the k-th submesh has size (jQ k
through j k of the original mesh. In the k-th submesh compute ARANN r
follows:
Step 3.1 Partition the k-th submesh of size (jQ k submeshes each
of size (jQ k Assign each point p in P k to each such submesh, and
compute d(p; q) for each point q in Q k .
Step 3.2 By using the algorithm of Lemma 3.2, compute the minimum of all d(p; q)
over all q in Q k in each submesh assigned to p and return the (0; r)-nearest
neighbor of p.
The reader should have no difficulty to confirm that Steps 1 and 2 can be performed in
constant time. By using the prefix-sums algorithm of Lemma 3.3, the partitioning in Step 3
can be performed in constant time. Steps 3.1 and 3.2 can also be implemented to run in
constant time. To summarize, we have proved the following result.
Lemma 4.6 If Minima(P ) and Maxima(Q) have been assigned to the columns and the rows,
respectively, of a RM of size n \Theta n ffl , then ARANN r (Minima(P ); Maxima(Q)) can be computed
in O(1) time for every fixed
We are now in a position to discuss an O(1) time implementation of Step 5 that computes
Z(p) for all p. For simplicity, assume that the RM has n \Theta 2n processors.
Step 5.1 Partition the n \Theta 2n RM columnwise into n 2=3 submeshes. For
be of size n \Theta (jX
Step 5.2 In each submesh R(i;
Step 5.3 In each submesh R(i;
Step 5.4 In each submesh R(i;
i;j )). If
Step 5.1 is complicated, because the number of columns of each submesh is different.
The partitioning specified in Step 5.1 can be completed in O(1) time by using the sorting
algorithm of Lemma 3.1: sort the n points in lexicographical order of (x 0 (p); y(p)). Clearly,
for each i and j, all points in X are consecutive in the sorted points. If the smallest
point in and the largest one are s-th and t-th in the sorted order, then the submesh
assigned columns s
Step 5.1 can be completed in O(1) time. Steps 5.2 can be completed as follows: Let
k. Compute the postfix-maxima of
g, by the algorithm of Lemma 3.2. Then,
and only if maxfy(p k+1 ); y(p k+2 ); y(p k+3 can be
computed in O(1) time. Step 5.3 can be completed in the same way. To apply the algorithm
of Lemma 4.6 to Step 5.4, a serial number must be assigned to the points in Minima(X
and those in Minima(Z 0
i;j ). These numbering can be obtained in the obvious way by using
the prefix-sum algorithm of Lemma 3.3. Then, by executing the algorithm of Lemma 4.6,
Step 5.4, can be completed in O(1) time. Therefore, ARANN r (S) can be computed in O(1)
time on an n \Theta 2n RM.
Since the algorithm above that uses n \Theta 2n processors, can be implemented on an n \Theta n
RM by a simple scheduling technique, ARANN r (S) can also be computed in O(1) time on
an n \Theta n RM. Furthermore, the ARANN r (S) for r -=2 can be computed by partition
the angle into several acute angles. For example, the ARANN 2-=3 (S) can be computed as
follows:
1. compute ARANN -=2 (S),
2. rotate all the points in S by an angle of -=2 clockwise about the origin,
3. compute ARANN -=6 (S), and
4. for each point, determined the nearest of the two points computed in 1 and 2 that
corresponds to the nearest point for ARANN 2-=3 (S).
Therefore, we have proved the following result.
Theorem 4.7 Given an arbitrary set of n points in the plane and a direction r, (0 ! r -
2-), the corresponding instance of the ARANN problem can be solved in O(1) time on a
reconfigurable mesh of size n \Theta n.
5 Application to Proximity Problems
The goal of this section is to show that the result of Theorem 4.7 leads to O(1) time algorithms
for the GNG and RNG and the EMST.
To begin, from Theorem 4.7, can be computed in O(1) time on
an n \Theta n RM. Therefore, we have
Corollary 5.1 Given n points in the plane, its GNG can be computed in O(1) time on a
reconfigurable mesh of size n \Theta n.
Since each GNG i is planar, GNG i has at most 3n \Gamma 6 edges and thus GNG has at most
edges. Furthermore, RNG is a subgraph of GNG [7]. Therefore, we have
Theorem 5.2 Given n points in the plane, the corresponding RNG can be computed in O(1)
time on an n \Theta n RM.
Proof. For each edge in GNG, check whether there is a point in its lune. If such a point
does not exist, this edge is an RNG edge, and vice versa. This checking can be done in O(1)
time by n processors for each edge. Since the GNG of n points has at most 18n \Gamma 36 edges,
the RNG can be computed in O(1) time on an n \Theta n RM. 2
Furthermore, by using the MST algorithm for Lemma 3.5, we have the following theorem.
Theorem 5.3 Given n points in the plane, its EMST can be computed in O(1) time on a
reconfigurable mesh of size n \Theta n 2 .
Proof. By applying the MST algorithm for a graph to the RNG, the EMST of n points
can be computed, because EMST is a subgraph of RNG. Since the RNG has at most 3n \Gamma 6
edges, an n \Theta n 2 RM is sufficient to compute EMST in O(1) time. 2
6 Concluding Remarks
We have shown an optimal algorithm on a reconfigurable mesh for computing the Angle
Restricted All Nearest Neighbor problem. By using this algorithm, we have also shown
optimal algorithms on a reconfigurable mesh for computing the Geographical Neighborhood
Graph and the Relative Neighborhood Graph. These algorithms are optimal in the sense
that there is no O(1)-time algorithm that solves instances of size n of these problems on an
reconfigurable mesh. Furthermore, we have also shown that the Euclidean
Minimum Spanning Tree of a set of n points in the plane can be computed in O(1) time on
an n \Theta n 2 reconfigurable mesh, provided that every processor can fuse its ports. It remains
open to find an O(1)-time EMST algorithm on an n \Theta n reconfigurable mesh that matches
the lower bound.



--R

Parallel Computational Geometry
The power of reconfiguration
Voronoi diagrams based on convex functions
Pattern Classification and Scene Analysis
Parallel geometric problems on the reconfigurable mesh
An optimal sorting algorithm on reconfigurable meshes
Computing relative neighborhood graphs in the plane

IEEE Transactions on Computers

Reconfigurable buses with shift switching - concepts and appli- cations
Sorting in O(1) time on a reconfigurable mesh of size N
IEEE Transactions on Parallel and Distributed Systems
Hardware support for fast reconfigurability in processor arrays
Parallel Computations on Reconfigurable Meshes
Connection autonomy in SIMD computers: a VLSI implemen- tation
Sorting n numbers on n
Fundamental Data Movement International Journal of High Speed Computing
Fundamental Algorithms on Reconfigurable Meshes
Computational Geometry - An Introduction
On the ultimate limitations of parallel processing
Bus automata
bit serial associate processor
The gated interconnection network for dynamic programming
the relative neighborhood graph with an application to minimum spanning trees
The relative neighborhood graph of a finite planar set
The symmetric all-furthest neighbor problem
Constant time algorithms for the transitive closure problem and its applications IEEE Transactions on Parallel and Distributed Systems
The image understanding architecture
--TR

--CTR
Hongga Li , Hua Lu , Bo Huang , Zhiyong Huang, Two ellipse-based pruning methods for group nearest neighbor queries, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany
Ramachandran Vaidyanathan , Jerry L. Trahan , Chun-ming Lu, Degree of scalability: scalable reconfigurable mesh algorithms for multiple addition and matrix-vector multiplication, Parallel Computing, v.29 n.1, p.95-109, January
Dimitris Papadias , Yufei Tao , Kyriakos Mouratidis , Chun Kit Hui, Aggregate nearest neighbor queries in spatial databases, ACM Transactions on Database Systems (TODS), v.30 n.2, p.529-576, June 2005
reconfigurable mesh;mobile computing;ARANN;proximity problems;lower bounds;ANN