  Let $S \subseteq \mathbb{R}^2$ be a set of $n$ \emph{sites} in the plane, so
that every site $s \in S$ has an \emph{associated radius} $r_s > 0$. Let $D(S)$
be the \emph{disk intersection graph} defined by $S$, i.e., the graph with
vertex set $S$ and an edge between two distinct sites $s, t \in 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(\alpha(n))$ amortized
query time and $O(\log^6 n)$ expected amortized insertion time.

Computational Geometry