VORONOI DIAGRAMS OVER DYNAMIC SCENES

Given a finite set S of n points in the Euclidean plane E2, we investigate the change of the Voronoi diagram VD(S) and its dual, the Delaunay triangulation DT(S), under continuous motions of the underlying points. It is the idea to use the topological dual of the Voronoi diagram that is shown to be locally stable under sufficiently small continuous motions, in opposite to the accompanying Voronoi diagram which is reconstructed from its dual only when it is needed. We present an efficient, numerically stable update algorithm for the topological structure of the Voronoi diagram in a dynamic scene, using only O(log n) time for each change (which is worst-case optimal). Furthermore, we develop fast algorithms for inserting and deleting points at the edge of the dynamic scene. There are a lot of related problems in computational geometry, as for example the dynamic convex hull and the dynamic nearest neighbor problem, but also applications in motion planning and pattern recognition in dynamic scenes.