Higher-order Voronoi Diagrams of Polygonal Objects

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 (or in any dimensional space) their Voronoi diagram divides the space into regions such that the Voronoi region of a site s is the locus of points closer to s than to any other site. Sites can be points, polygonal objects, or any other type of geometric object. Voronoi diagrams can be defined over any metric and in any dimension. Higher order Voronoi diagrams (Voronoi diagrams of order-k) encode k-nearest neighbor information and they define a partitioning of space into maximal regions such that every point within a region has the same k nearest sites. Geometric scenarios occurring in practice are often modeled by polygonal objects. In this respect, generalized Voronoi diagrams of polygonal objects are of particular importance. This project continues the investigation of higher order Voronoi diagram of polygonal objects that started in SNF project 200021-127137. The goal is the design of efficient algorithms to construct the order-k Voronoi diagram of such objects, including line segments and convex polygons. Polygons, introduce complications that are not present in the case of points or even line-segments. For example, the bisector of two convex polygons may be undefined, and the bisector of two simple polygons may be a closed curve. Higher order Voronoi diagrams under these conditions have not been considered in the computational geometry literature. The work is important from both a theoretical and an application point of view as it investigates fundamental geometric structures, central in the field of computational geometry, which have been motivated by industrial applications in VLSI Design Automation and may have direct impact to CAD technologies for semiconductor manufacturing.