Constructing higher-order Voronoi diagrams in parallel.
Henning Meyerhenke · 2005
We use Lee’s sequential algorithm [17] to create the first parallel algorithm which constructs the order-k Voronoi diagram of a planar point set. The algorithm is developed and analyzed within two parallel models, the fine-grained PRAM and the coarse-grained CGM. Its applications include k-nearest neighbor searches in a parallel context, which are important for many applications in computational geometry. The fine-grained algorithm requires O(klog2n) time and O(k2nlogn) work on a CREW-PRAM, whereas the coarse-grained version requires the ordinary Voronoi diagram as input and then takes O ( k2 (n−k) log n p) running time and O(k) communication rounds on a CGM with O ( k2 (n−k) p) local memory per processor. same k nearest neighbors (thus, an ordinary Voronoi diagram has order one). An example of the order-2 diagram of a planar point set is depicted in figure 1. Previous works on sequential algorithms for constructing higher order Voronoi diagrams include the books of Preparata and Shamos [18] and Edelsbrunner [13]. The latter points out the duality between k-levels in arrangements and higher order Voronoi diagrams, an idea which is used in some of the sequential algorithms developed for the posed problem by