A cellular automata based algorithm for voronoi diagram of arbitrary shapes

Presented in this paper is a cellular automata based algorithm for computing voronoi diagram of arbitrary shapes. There is no limitation for sites; they can be circles, rectangles, points or anything else. Our algorithm outperforms previous works in speed and accuracy. The proposed algorithm constructs the correct voronoi diagram as a wave from each site is propagated to the environment. When waves collide to each others, the borders of voronoi cells are built. We used asynchronous CA that made our algorithm faster. Our algorithm can be used in distributed systems and supposed as a parallel strategy to build voronoi diagram of arbitrary shapes.