A Note On CommunicationEfficient Deterministic Parallel Algorithms for Planar Point Location and 2d Voronoi Diagram. 

M. Diallo, A. Ferreira, and A. RauChaplin 

Abstract: In this note we describe deterministic parallel algorithms for planar point location and for building the Voronoi Diagram of $n$ coplanar points. These algorithms are designed for BSP/CGMlike models of computation, where $p$ processors, with $O(\frac{n}{p}) \gg O(1) $ local memory each, communicate through some arbitrary interconnection network. They are communicationefficient since they require, respectively, $O(1)$ and $O(\log p)$ communication steps and $O(\frac{n \log n}{p})$ local computation per step. Both algorithms require $O(\frac{n}{p}) = \Omega(p) $ local memory. 

paper.pdf 
paper.ps 

