A Note on Communication-Efficient Deterministic Parallel Algorithms for Planar Point Location and 2D Voronoï Diagram
Mohamadou Diallo · Parallel Processing Letters · 2001
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 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 local computation per step. Both algorithms require local memory.