In this paper we give a fully dynamic data structure to maintain the connectivity of the intersection graph of n axis-parallel rectangles. The amortized update time (insertion and deletion of rectangles) is O(n~(10/11) polylogn) and the query time (deciding whether two given rectangles are connected) is O(1). It slightly improves the update time (O(n~(0.94))) of the previous method while drastically reducing the query time (near O(n~(1/3))). Our method does not use fast matrix multiplication results and supports a wider range of queries.
展开▼
