1989-01-01
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 | |
|---|---|
| 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
|