While the voronoi diagram of a continuously moving set of points in
the plane is constantly changing, the graph structure of the dual of
the voronoi diagram (the Delaunay triangulation), remains locally
stable for short periods of continuous motion of the underlying
points. Specific geometric conditions can be derived for when the
Delaunay triangulation changes and what kinds of transformations the
graph can undergo. These limitations make it possible to optimally
update the Delaunay triangulation of a dynamic scene.
These are results from a paper by Thomas Roos, Discrete Applied
Mathematics, 1993, vol 43.