Dynamic Voronoi Diagram for Moving Disks
Chanyoung Song, Jehyun Cha, Mokwon Lee, Deok‐Soo Kim · IEEE Transactions on Visualization and Computer Graphics · 2019
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^{\infty })$. The proposed TOI-E algorithm computes the event history of the Voronoi diagram over the entire time horizon in$O(k_F \log n + k_C n \log n)$time with$O(n \log n)$preprocessing time and$O(n + k_F + k_C)$memory for$n$disk generators,$k_F$edge flips, and$k_C$disk collisions during the time horizon. Given an event history, the Voronoi diagram of an arbitrary moment$t^{\ast}