Insertion-Only Dynamic Connectivity in General Disk Graphs
share
Let S ⊆ℝ^2 be a set of n sites in the plane, so that every site s ∈ S has an associated radius r_s > 0. Let D(S) be the disk intersection graph defined by S, i.e., the graph with vertex set S and an edge between two distinct sites s, t ∈ S if and only if the disks with centers s, t and radii r_s, r_t intersect. Our goal is to design data structures that maintain the connectivity structure of D(S) as S changes dynamically over time. We consider the incremental case, where new sites can be inserted into S. While previous work focuses on data structures whose running time depends on the ratio between the smallest and the largest site in S, we present a data structure with O(α(n)) amortized query time and O(log^6 n) expected amortized insertion time.
READ FULL TEXT