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

M. Diallo, A. Ferreira, and A. Rau-Chaplin

Abstract: In this note we describe deterministic parallel algorithms for planar point location and for building the Voronoi Diagram of $n$ co-planar points. These algorithms are designed for BSP/CGM-like 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 communication-efficient 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.