Kinetic connectivity of rectangles
John E. Hershberger, Subhash Suri · 1999
We develop a kinetic data structure (KDS) for maintaining the connectivity of a set of axis-aligned rectangles moving in the plane. In the kinetic framework, each rectangle is assumed to travel along a low-degree algebraic path, specified by a flight plan---if the flight plan changes, the data structure is informed about it. The connectivity of rectangles changes only at discrete moments, given by the times when the order of rectangles along either axis changes. Our main result is a kinetic data structure of size O(n log n) that requires O(log 2 n) amortized time for each update, and answers connectivity queries in worst-case time O(log n= log log n). 1 Introduction Connectivity is the most basic of graph properties, with many applications to real-world problems. Applications of connectivity range from electrical connectivity in integrated circuits to network connectivity in communication networks. In this paper, we explore the problem of maintaining the connectivity of n axis-alig...