VORONOI++ - VORONOI++

This project is concerned with a versatile structure called the Voronoi diagram, which illustrates the influence that a given set of geometric sites exert on their surrounding space. Space-partitioning structures of this kind have been known since the 17th century, and they have successfully been applied to solve spatial problems. In this project, we focus on “cluster Voronoi diagrams”, where sites are sets (clusters) of simple geometric objects in the plane. Such diagrams provide subdivisions of the plane into maximal regions such that each region reveals proximity information for the input clusters or for clusters of the input sites. We plan to investigate open problems related to the so called farthest color Voronoi diagram (FCVD), the Hausdorff Voronoi diagram (HVD), and the order-k Voronoi diagram, including the farthest-site Voronoi diagram (where k = n – 1). Open problems include the following: Identifying conditions under which the FCVD is a tree structure, or it has linear combinatorial complexity, and design efficient algorithms to construct it. Investigate algorithms for computing the FCVD and HVD in their generality. Define the order-k color Voronoi diagram of a given family of clusters. Investigate linear-time construction algorithms for tree-like Voronoi diagrams (like those that appear in order-k and farthest diagrams). The Voronoi diagram is an influential structure playing an important role in natural sciences, economics, and engineering. This project will increase our knowledge on this powerful geometric object. The problems that we plan to investigate in this project stem out of applications related to facility location, wireless sensor networks, and VLSI design.