1. A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams
- Author
-
Anil Maheshwari, Frank Dehne, and Ryan Taylor
- Subjects
Computational complexity theory ,Computer science ,Open problem ,Computer cluster ,Parallel algorithm ,Hausdorff space ,Parallel computing ,Computational geometry ,Voronoi diagram ,Algorithm - Abstract
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 time 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 non-crossing objects in time O(n log4 n). This improves on previous sequential results and solves an open problem posed by Papadopoulou and Lee (2004)
- Published
- 2006
- Full Text
- View/download PDF