Dynamic Voronoi Diagram for Moving Disks.

Voronoi diagrams are powerful for understanding spatial properties. However, few reports have been made for moving generators despite their important applications. We present a topology-oriented event-increment (TOI-E) algorithm for constructing a Voronoi diagram of moving circular disks in the plane over the time horizon [0, t). The proposed TOI-E algorithm computes the event history of the Voronoi diagram over the entire time horizon in O(k logn + k n logn) time with O(n logn) preprocessing time and O(n + k + k) memory for n disk generators, k edge flips, and k disk collisions during the time horizon. Given an event history, the Voronoi diagram of an arbitrary moment can be constructed in O(k + n) time where k represents the number of events in [0, t). An example of the collision avoidance problem among moving disks is given by predicting future conjunctions among the disks using the proposed algorithm. Dynamic Voronoi diagrams will be very useful as a platform for the planning and management of the traffics of unmanned vehicles such as cars on street, vessels on surface, drones and airplanes in air, and satellites in geospace.