Voronoi diagrams

The Voronoi diagram of a set of objects in a space is the partition of this space in regions in such a way that points of the same region have the same objects as the nearest or farthest objects. We are interested in compute approximated Voronoi diagrams in the plane, in the 3D space or on terrains. In the last case, we study how to properly compute distances on terrains.

Voronoi diagram of 4 objects

in the plane. Each object has

an own distance function.

Voronoi diagram of 15

spheres in the 3D space

Voronoi diagram of the nearest

object on a terrain

Voronoi diagram of the farthest

object on a terrain

Distance field of 5 generalized

sources, darker points are

closer to sources

Voronoi diagram of 5 generalized

sites on a weighted triangulated

terrain

Furthest Voronoi diagram of 5

generalized sites on a wieghted

triangulated terrain, colors

2nd nearest neighbor Voronoi

diagram of 5 generalized sites

on a weighted triangulated terrain

2nd order Voronoi diagram, point

with the same color have the same

set of two nearest neighbors

Voronoi diagram of 100 sites randomly places on the

NewYork road network.

7th nearest voronoi diagram on a road network

which contains 25 sites

Reverse 7th nearest neighbor query. The green sites

have the red one as one of the 7th nearest sites