Ryan Taylor
The Voronoi Diagram is a standard structure in Computational Geometry and has been well studied. Researchers have also studied many variations of the standard Voronoi Diagram. Recent research has been presented on one such variation, the Hausdorff Voronoi Diagram. This particular geometric construction has interesting applications in the Engineering field of VLSI manufacturing.
Due to the large problem sets required in practice, the construction of Hausdorff Voronoi Diagrams presents an ideal problem for parallelization. The CGM parallel computing model has proven to be a useful model for the design of practical parallel algorithms.
This talk will first review the Hausdorff Voronoi Diagram. We then focus on research to design a CGM parallel algorithm for constructing Hausdorff Voronoi Diagrams. We conclude with some results gained by implementing this algorithm.