Simplified kinetic connectivity for rectangles and hypercubes
John E. Hershberger, Subhash Suri · Symposium on Discrete Algorithms · 2001
We consider the problem of maintaining connected components in a set of moving objects using the kinetic data structure (KDS) framework. We assume that the motion of each object can be specified by a low-degree algebraic trajectory; this trajectory, however, can be modified in an on-line fashion. While the objects move continuously, their connectivity changes at discrete times. A straightforward dynamic graph approach for maintaining connectivity of n objects has three shortcomings: the graph can have O(n2) edges, the update bounds are amortized, and the algorithm is very complicated. Our first result shows that the connectivity for a set of n moving hypercubes can be maintained using a very simple, easy to determine graph with O(n) edges. But this graph still requires a general-purpose dynamic graph scheme for connectivity maintenance. Our main result is a simplified connectivity data structure for moving rectangles in the plane. For this special but important case, we are able to overcome all three shortcomings mentioned above: our graph has O(n) edges; our data structure supports updates in O(log2n) worst-case time; and the algorithm and data structures are quite a bit simpler than those based on a general dynamic graph scheme.