Kinetic connectivity for unit disks
Leonidas Guibas, John E. Hershberger, Subhash Suri, Li Guo Zhang · 2000
We describe a kinetic data structure (KDS) that maintains the connected components of the union of a set of unit-radius disks moving in the plane. We assume that the motion of each disk can be specified by a low-degree algebraic trajectory; this trajectory, however, can be modified in an on-line fashion. While the disks move continuously, their connectivity changes at discrete times. Our main result is an O(n) space data structure that takes O(log n/ log log n) time per connectivity query of the form "are disks A and B in the same connected component?" A straightforward approach based on dynamically maintaining the overlap graph requires## n 2 ) space. Our data structure requires only linear space and must deal with O(n 2+# ) updates in the worst case, each requiring O(log 2 n) amortized time. This number of updates is close to optimal, since a set of n moving unit disks can undergo## n 2 ) connectivity changes. 1 Introduction Motivated by applications in mobile ...