In this paper, we present a systolic algorithm for computing the configuration space of an arrangement of arbitrary obstacles in the plane for a rectilinearly convex robot. The obstacles and the robot are assumed to be represented in digitized form by a √n × √n nibary image. The algorithm is designed for a Mesh-of-Processors architecture with n processors (using the canonical representation of an image on a processor array) and has an execution time of O(√n) which is asymptotically optimal.

, , ,
doi.org/10.1016/0167-8191(89)90055-0
Parallel Computing
School of Computer Science

Dehne, F, Hassenklover, A.-L. (Anne-Lise), & Sack, J.-R. (1989). Computing the configuration space for a robot on a mesh-of-processors. Parallel Computing, 12(2), 221–231. doi:10.1016/0167-8191(89)90055-0