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.

Additional Metadata
Keywords Computational geometry, image processing, robotics, systolic algorithms
Persistent URL dx.doi.org/10.1016/0167-8191(89)90055-0
Journal Parallel Computing
Citation
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