On the possibility of simple parallel computing of Voronoi diagrams and Delaunay graphs

Abstract

The Voronoi diagram is a widely used data structure. The theory of algorithms for computing Euclidean Voronoi diagrams of point sites is rich and useful, with several different and important algorithms. However, this theory has been quite steady during the last few decades in the sense that new algorithms have not entered the game. In addition, most of the known algorithms are sequential in nature and hence cast inherent difficulties on the possibility to compute the diagram in parallel. This paper presents a new and simple algorithm which enables the (combinatorial) computation of the diagram. The algorithm is significantly different from previous ones and some of the involved concepts in it are in the spirit of linear programming and optics. Parallel implementation is naturally supported since each Voronoi cell can be computed independently of the other cells. A new combinatorial structure for representing the cells (and any convex polytope) is described along the way and the computation of the induced Delaunay graph is obtained almost automatically.