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].

Additional Metadata
Persistent URL dx.doi.org/10.1109/ICPP.2006.5
Conference ICPP 2006: 2006 International Conference on Parallel Processing
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