| Dynamic connectivity for axis-parallel rectangles (2006) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. 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 polylog n) and the query time (deciding whether two given rectangles are connected) is O(1). It slightly improves the update time (O(n | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||