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.