Dynamic Geometric Connectivity in the Plane with Constant Query Time

We present the first fully dynamic connectivity data structures for geometric intersection graphs achieving constant query time and sublinear amortized update time for many classes of geometric objects in 2D. Our data structures can answer connectivity queries between two objects, as well as “global” connectivity queries (e.g., deciding whether the entire graph is connected). Previously, the data structure by Afshani and Chan (ESA’06) achieved such bounds only in the special case of axis-aligned line segments or rectangles but did not work for arbitrary line segments or disks, whereas the data structures by Chan, Pătraşcu, and Roditty (FOCS’08) worked for more general classes of geometric objects but required n^Ω(1) query time and could not handle global connectivity queries. Specifically, we obtain new data structures with O(1) query time and amortized update time near n⁴/⁵, n⁷/⁸, and n²⁰/²¹ for axis-aligned line segments, disks, and arbitrary line segments respectively. Besides greatly reducing the query time, our data structures also improve the previous update times for axis-aligned line segments by Afshani and Chan (from near n¹⁰/¹¹ to n⁴/⁵) and for disks by Chan, Pătraşcu, and Roditty (from near n²⁰/²¹ to n⁷/⁸).