1989
Computing the configuration space for a robot on a mesh-of-processors
Publication
Publication
Parallel Computing , Volume 12 - Issue 2 p. 221- 231
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 | |
|---|---|
| Computational geometry, image processing, robotics, systolic algorithms | |
| dx.doi.org/10.1016/0167-8191(89)90055-0 | |
| Parallel Computing | |
| Organisation | 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
|
|