Information Technology Reference
In-Depth Information
Label Component T
Loc a l Topmost
Loca l Bottommost
Loc a l Topmost
Loca l Bottommost
Loc a l Topmost
Loca l Bottommost
Figure 19.2. An example for finding T label component in Algorithm 19.1.3 [23].
It should be noted that there is no static stage in this algorithm; it is done in
O(1) time per systolic cycle, which is the fastest solution for this problem.
&
19.1.2. Convex Hull Problem
Now we consider the convexity problem. We use the following definition of
convexity: A set of PEs is said to be convex if and only if the corresponding set of
integer lattice points is convex. Given a set S of PEs, the convex hull of S, denoted
Hull (S), is the smallest convex set of PEs containing S.
In the following, first we show that if the size of the image is the same as that
of the reconfigurable mesh, the convex hull of a single figure can be found in
O(log N) time. Then we show that if the size of the reconfigurable mesh is N times
larger than the size of the image, the above algorithm time complexity becomes
O(1). We also show that the convex hull of multiple (up to N) figures can be found
in O(log N).
Algorithm 19.1.4
Given an N N image, using an N N Spin-Wave reconfigurable mesh, the convex
hull of a single figure can be found in O(log N) time.
This algorithm operates in two steps. First the rightmost (RM) and the
leftmost (LM) black pixels (1-valued) in each row are found. Then it will be
verified if these points are extreme points or not.
Step 1: Fist all the left and right switches of each node are tuned on, so that all the
channels between the nodes in the same row are open. Then each black node sends
out a 1 signal on the bus and turns off its left-hand side switch, thereby closing that
Search WWH ::




Custom Search