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.
in the plane. Each object has
an own distance function.
Voronoi diagram of 15
spheres in the 3D space
spheres in the 3D space
Voronoi diagram of the nearest
object on a terrain
object on a terrain
Voronoi diagram of the farthest
object on a terrain
object on a terrain
Distance field of 5 generalized
sources, darker points are
closer to sources
sources, darker points are
closer to sources
Voronoi diagram of 5 generalized
sites on a weighted triangulated
terrain
sites on a weighted triangulated
terrain
Furthest Voronoi diagram of 5
generalized sites on a wieghted
triangulated terrain, colors
generalized sites on a wieghted
triangulated terrain, colors
2nd nearest neighbor Voronoi
diagram of 5 generalized sites
on a weighted triangulated terrain
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
with the same color have the same
set of two nearest neighbors
Voronoi diagrams are used to efficiently solve proximity
problems or in robot path planning.
problems or in robot path planning.
Roadnetworks and facility location problems
Voronoi diagram of 100 sites randomly places on the
NewYork road network.
NewYork road network.
7th nearest voronoi diagram on a road network
which contains 25 sites
which contains 25 sites
Reverse 7th nearest neighbor query. The green sites
have the red one as one of the 7th nearest sites
have the red one as one of the 7th nearest sites