We present the first parallel algorithm for building a Hausdorff Voronoi diagram (HVD). Our algorithm is targeted towards cluster computing architectures and computes the Hausdorff Voronoi diagram for non-crossing objects in lime O(n log4 n/p} for input size n and p processors. In addition, our parallel algorithm also implies a new sequential HVD algorithm that constructs HVDs for noncrossing objects in time O(n log4 n). This improves on previous sequential results and solves an open problem posed by Papadopoulou and Lee [118].

ICPP 2006: 2006 International Conference on Parallel Processing
School of Computer Science

Dehne, F, Maheshwari, A, & Taylor, R. (Ryan). (2006). A coarse grained parallel algorithm for Hausdorff Voronoi diagrams. Presented at the ICPP 2006: 2006 International Conference on Parallel Processing. doi:10.1109/ICPP.2006.5