Generalized Voronoi Diagrams of Polygonal Objects: Algorithms and Applications

We will investigate open problems on generalized Voronoi diagrams of polygonal objects in the plane. Voronoi diagrams are among the most fundamental structures in Computational Geometry and they have proved to be powerful tools in solving diverse and seemingly unrelated computational problems. The basic concept is simple: given a number of sites in the plane, their Voronoi diagram divides the space into regions such that the Voronoi region of a site s is the locus of points closest to s than to any other site. Sites can be points, polygonal objects, or any other type of geometric object. Generalized Voronoi diagrams of higher order-k generalize this notion to more than one site. They define a partitioning of space into maximal regions such that every point within a region has the same k nearest sites. The Hausdorff Voronoi diagram is another generalization of Voronoi diagrams, defined on clusters of points, where the distance between a point t and a cluster P is measured according to the maximum distance between t and all elements in P, and the Hausdorff Voronoi region of P is the locus of points closer to P than to any other cluster. In this project, we plan to investigate open questions related to the following problems: the higher order Voronoi diagram of line segments, the higher order Hausdorff Voronoi diagram, and the geometric min-cut problem. The geometric min cut problem is an interesting variant of the classic min cut problem in graphs and it is related to both Voronoi diagrams and graph connectivity. Our work will combine the combinatorial and structural analysis of these fundamental geometric structures, the design and analysis of efficient algorithms for their construction, as well as implementation and application issues. The problems under investigation are fundamental combinatorial structures central in the field of computational geometry that are interesting on their own right. In addition, they have been motivated by application problems and their solution can have direct impact on emerging CAD technologies for VLSI Manufacturability and other applications.