Kinetic Connectivity for Unit Disks

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\slash \kern -1pt 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 ² ) space. Our data structure requires only linear space and must deal with O(n ^{2 + ε} ) updates in the worst case, each requiring O(log ² n) amortized time, for any ε>0 . This number of updates is close to optimal, since a set of n moving unit disks can undergo Ω (n ² ) connectivity changes. Received September 20, 2000, and in revised form January 19, 2001. Online publication April 6, 2001.