In a partitioned optical passive stars (POPS) network, n=dg processors are divided into g groups of d processors each, and such a POPS network is denoted by POPS(d,g). There is an optical passive star (OPS) coupler between every pair of groups. Hence, a POPS(d,g) requires g/sup 2/ couplers. It is likely that, in a practical system, the number of couplers will be less than the number of processors, i.e., d>/spl radic/n>g and the number of groups will be smaller than the number of processors in a group. Hence, it is important to design fast algorithms for basic operations on such POPS networks with large group size. We present fast algorithms for data sum, prefix sum, and permutation routing on a POPS(d,g) such that d>/spl radic/n>g. Our data sum and prefix sum algorithms improve upon the best known algorithms for these problems designed by Sahni (2000). Permutation routing can be solved on a POPS network by simulating a hypercube sorting algorithm. Our algorithm for permutation routing is more efficient compared to this simulated hypercube sorting algorithm.

We present an O((log log N)/sup 2/) -time algorithm for computing the distance transform of an N /spl times/ N binary image. Our algorithm is designed for the common concurrent read concurrent write parallel random access machine (CRCW PRAM) and requires O(N/sup 2+/spl epsi///log log N) processors, for any /spl epsi/ such that 0 < /spl epsi/ < 1. Our algorithm is based on a novel deterministic sampling scheme and can be used for computing distance transforms for a very general class of distance functions. We also present a scalable version of our algorithm when the number of processors is available p/sup 2+/spl epsi///log log p for some p < N. In this case, our algorithm runs in O((N/sup 2//p/sup 2/)+(N/p) log log p + (log log p)/sup 2/) time. This scalable algorithm is more practical since usually the number of available processors is much less than the size of the image.

We present two fast algorithms for sorting on a linear array with a reconfigurable pipelined bus system (LARPBS), one of the recently proposed parallel architectures based on optical buses. In our first algorithm, we sort N numbers in O(log N log log N) worst-case time using N processors. In our second algorithm, we sort N numbers in O((log log N)/sup 2/) worst-case time using N/sup 1+/spl epsi// processors, for any fixed /spl epsi/ such that 0 < /spl epsi/ < 1. Our algorithms are based on a novel deterministic sampling scheme for merging two sorted arrays of length N each in O(log log N) time on an LARPBS with N processors. To our knowledge, the previous best sorting algorithm on this architecture has a running time of O((log N)/sup 2/) using N processors.

The Euclidean distance transform (EDT) is an operation to convert a binary image consisting of black and white pixels to a representation where each pixel has the Euclidean distance of the nearest black pixel. The EDT has many applications in computer vision and image processing. In this paper, we present an algorithm for computing the EDT of a binary image on the Linear Array with a Reconfigurable Pipelined Bus System (LARPBS), a recently proposed architecture based on optical buses. Our algorithm is deterministic and runs in time for a binary image on an LARPBS with processors, for any fixed , . We also show that our algorithm is highly scalable. If the LARPBS has only processors for , our algorithm runs in time. The algorithm

We consider the navigation problem of a robot from a starting point S to a target point T inside an unknown polygonal environment. The robot knows the directions of the points S and T and it can detect the walls of the environment through its tactile sensors. We present a competitive strategy for the robot to reach the target T. The path length generated by the robot is /spl les/4.5d(/spl kappa/-1)(/spl kappa/+2)/spl times/d, where, /spl kappa/=3/sup (d/2-1)/ and d is the L/sub 1/ distance between S and T.