Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs

A classical problem in computational geometry and graph algorithms is: given a dynamic set S of geometric shapes in the plane, efficiently maintain the connectivity of the intersection graph of S. Previous papers studied the setting where, before the updates, the data structure receives some parameter P. Then, updates could insert and delete disks as long as at all times the disks have a diameter that lies in a fixed range [1/P , 1]. As a consequence of that prerequisite, the aspect ratio ψ (i.e. the ratio between the largest and smallest diameter) of the disks would at all times satisfy ψ ≤ P. The state-of-the-art for storing disks in a dynamic connectivity data structure is a data structure that uses O(P n) space and that has amortized O(P log⁴ n) expected amortized update time. Connectivity queries between disks are supported in O(log n/ log log n) time.
In the dynamic setting, one wishes for a more flexible data structure in which disks of any diameter may arrive and leave, independent of their diameter, changing the aspect ratio freely. Ideally, the aspect ratio should merely be part of the analysis. We restrict our attention to axis-aligned squares, and study fully-dynamic square intersection graph connectivity. Our result is fully-adaptive to the aspect ratio, spending time proportional to the current aspect ratio ψ, as opposed to some previously given maximum P. Our focus on squares allows us to simplify and streamline the connectivity pipeline from previous work. When n is the number of squares and ψ is the aspect ratio after insertion (or before deletion), our data structure answers connectivity queries in O(log n/ log log n) time. We can update connectivity information in O(ψ log4 n + log6 n) amortized time. We also improve space usage from O(P · n log n) to O(n log³ n log ψ) – while generalizing to a fully-adaptive aspect ratio – which yields a space usage that is near-linear in n for any polynomially bounded ψ.