Algorithmic Advances in Voronoi diagrams and Nearest-Neighbor queries

Elena Arseneva will be hosted at USI as a researcher within the project: Algorithmic Advances in Voronoi diagrams and Nearest-Neighbor queries Voronoi diagrams are among the most fundamental and influential structures in Computational Geometry. Given a set of n simple geometric objects, called sites, their Voronoi diagram subdivides the surrounding space into regions of influence exerted by the given sites. The classic nearest-neighbor Voronoi diagram reveals information on the nearest neighbor of every site and higher-order Voronoi diagrams reveal k-nearest neighbor information. In cluster Voronoi diagrams, the sites are sets (clusters) of simple geometric objects and the diagram may provide min-max or max-min type of proximity information. This project aims to answer algorithmic open questions related to this influential structure and its applications, organized around the following activities.