Swap conditions for dynamic Voronoi diagrams for circles and line segments

Dynamic maintenance of Voronoi diagrams for a set of disks moving independe ntly in the plane along given trajectories is considered in this paper. The domain is limited by boundary represented by straight-line segments. Maint enance of a Voronoi diagram for moving objects (disks and/or line segments) over time requires calculation of topological events which occur when four objects arrive at positions where they are tangent to a common circle. Cri teria for determination of such topological events for circles and line seg ments in the Euclidean metric have been derived using a standard fractional transformation in complex plane. These criteria are represented in the for m of polynomial algebraic equations, based on the coordinates and trajector ies of the moving objects. These equations can normally only be solved usin g numerical methods. (C) 1999 Elsevier Science B.V. All rights reserved.