A parallel algorithm to construct Voronoi diagram and its VLSI architecture

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.