A Note on Communication-Efficient Deterministic Parallel Algorithms for Planar Point Location and 2d Voronoï Diagram

In this note we describe deterministic parallel algorithms for planar point location and for building the Voronoï Diagram of n co-planar points. These algorithms are designed for BSP/CGM-like models of computation, where p processors, with O ( n) O(1) local memory p 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( local computation per step. Both algorithms require O ( n) = (p) local memory