2006-12-01
A coarse grained parallel algorithm for Hausdorff Voronoi diagrams
Publication
Publication
Presented at the
ICPP 2006: 2006 International Conference on Parallel Processing (August 2006)
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 |
| Citation |
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
|