Title :
A parallel algorithm to construct Voronoi diagram and its VLSI architecture
Author :
Sudha, N. ; Nandi, S. ; Sridharan, K.
Author_Institution :
Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Panbazar, India
Abstract :
This paper presents a parallel algorithm for computing the Voronoi diagram for collision-free path planning of robots. The algorithm constructs the Voronoi diagram on a binary image of the workspace and is based on the Euclidean distance function. It has been implemented in ANSI-C on an HP workstation. The algorithm is suitable for VLSI implementation in a cellular architecture. Such an architecture is described. Comparisons with an existing algorithm are also presented
Keywords :
VLSI; cellular arrays; computational geometry; computer vision; parallel algorithms; path planning; robots; Euclidean distance; VLSI architecture; Voronoi diagram; binary image; cellular architecture; parallel algorithm; path planning; robots; Computer architecture; Computer science; Euclidean distance; Orbital robotics; Parallel algorithms; Parallel robots; Path planning; Pixel; Robot kinematics; Very large scale integration;
Conference_Titel :
Robotics and Automation, 1999. Proceedings. 1999 IEEE International Conference on
Conference_Location :
Detroit, MI
Print_ISBN :
0-7803-5180-0
DOI :
10.1109/ROBOT.1999.770351
