Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

CGGC Seminar: An algorithm for computing Voronoi diagrams of general generators in general spaces
event speaker icon
Daniel Reem (Mathematics, Technion)
event date icon
Sunday, 24.05.2009, 13:00
event location icon
Taub 401 (note special room)
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.