NANOSCALE IMAGE PROCESSING - Bio-Inspired and Nanoscale Integrated Computing - page 522

y

RM i

x

Figure 19.4. Enclosing Angle X RM i Y[23].

column, assume in column c, no node has a value greater than the one in row c.
Thus the element in row and column c is the maximum angle. Since all these
comparisons are performed simultaneously, the time complexity is O(1).

Algorithm 19.1.6
The convex hull of multiple (N) figures in a given N N image using an N N spin-
wave reconfigurable mesh can be found in O(logN) time.

To find the convex hull of multiple (N) figures in an image with size of N,
using a spin-wave reconfigurable mesh of size N N, we can simulate each step of
the algorithm explained in [25] in constant time. So the total time complexity will
be O(log N).

&

19.1.3. The Nearest Neighbor Problem
In this problem we would like to find the closest neighbor of a specific figure. In the
following algorithm, first it is shown that for an image size equal to the size of the
spin-wave reconfigurable mesh, for a single figure, its nearest neighbor can be found
in O(logN) time. The same problem is next solved in O(1) time for another scenario
where the size of the reconfigurable mesh is N times larger than the size of the image.

Algorithm 19.1.7
Given an N N image, using an N N spin-wave reconfigurable mesh, the nearest
neighbor of a single figure can be found in O(log N) time.

In this stage, it is assumed that the figures are labeled and their convex hulls
are found. The time complexity of labeling and finding the convex hull are
O(log N), as mentioned in the previous sections. First we set up the switches so
that all nodes in the whole image are connected to each other. To find the neatest
neighbor of a figure, we should find the closest 1 (belonging to another figure) to
all the extreme points of this figure. To do so, each extreme point of the figure
broadcasts its address, as well as its ID, to all four directions. As soon as a black
node from another figure (with a different ID) receives this broadcasted signal, it
computes its distance to that node. Next, it sends this computed distance back to
the original node. It also blocks the channel by turning off its switch and does not
let the signal pass though.