The Taub Faculty of Computer Science Events and Talks

Voronoi diagrams appear in many areas in science and technology and have diverse applications. Roughly speaking, they are a certain decomposition of a given space into cells, induced by a distance function and by a tuple of subsets called the generators or the sites. Voronoi diagrams have been the subject of extensive research during the last 35 years, and many algorithms for computing them have been published. However, these algorithms are for specific cases. They impose various restrictions on the space (often R^2 or R^3), the generators (distinct points, special shapes), the distance function (Euclidean or variations thereof) and more. Moreover, their implementation is not always simple and their success is not always guaranteed.

We present and analyze an efficient and simple algorithm for computing Voronoi diagrams in general normed spaces, possibly infinite dimensional. We allow infinitely many generators of a general form. The algorithm computes each of the Voronoi cells independently of the others, and to any required precision. It is also generalized to other settings, such as manifolds, graphs and convex distance functions. We also discuss the question of stability, and as a by-product we obtain the geometric stability of Voronoi diagrams under small perturbations of the generators in a class of normed spaces.