Hausdorff and Higher-Order Voronoi Diagrams

This project will investigate fundamental open problems related to Hausdorff and higher-order Voronoi diagrams. The objective is to derive a deeper understanding of these basic structures, link them with the existing theoretical framework, and produce efficient but simple algorithms for their construction. Diverse application areas, such as the area of VLSI yield analysis and design manufacturability (DFM), can directly benefit from such algorithms. Specifically, we plan to investigate the following problems:The Hausdorff Voronoi diagram of clusters of line-segments, more generally, the Hausdorff Voronoi diagram of clusters of polygonal objects, and abstract Hausdorff Voronoi diagrams. We will investigate different types of Hausdorff Voronoi diagrams, starting with the Hausdorff Voronoi diagram of clusters of line-segments. The Hausdorff Voronoi diagram of clusters of line segments is a natural generalization of the point cluster Hausdorff Voronoi diagram, which has been motivated by applications. In addition, we plan to investigate whether various Hausdorff Voronoi diagrams can be unified under a common abstract umbrella as ordinary Voronoi diagrams can. Abstract Voronoi diagrams are defined in terms of bisecting curves and they offer a unifying framework for many instances of concrete Voronoi diagrams.Higher order Voronoi diagrams. We plan to explore the tight connection between Hausdorff Voronoi diagrams and higher-order Voronoi diagrams with the purpose of deriving simpler algorithms (e.g., plane sweep) to compute higher-order Voronoi diagrams even for the standard case of points, and expand the results to more general types of objects. Higher-order Voronoi diagrams are natural generalizations of the classic Voronoi diagram. In addition, we plan to explore the problem of unifying various concrete higher order Voronoi diagrams under the unifying concept of abstract Voronoi diagrams, in collaboration with CRP partner Rolf Klein. Generalized Voronoi diagrams in simpler non-Euclidean (piecewise linear) metrics such as the L-infinity/ L-1 metrics. We plan to investigate possible simplifications in the structural complexity of generalized Voronoi diagrams in the L-infinity metric such as the farthest line segment Voronoi diagram, higher order Voronoi diagrams, and Hausdorff Voronoi diagrams. In addition, we plan to investigate software design and implementation issues for variants of L-infinity Voronoi diagrams. Ultimate goal (not explicitly included as a deliverable in this project) is the creation of open source code (CGAL based, http://www.cgal.org/) for the construction of different versions of generalized L-infinity Voronoi diagrams targeting VLSI applications.