  A data structure is presented that explicitly maintains the graph of a
Voronoi diagram of $N$ point sites in the plane or the dual graph of a convex
hull of points in three dimensions while allowing insertions of new
sites/points. Our structure supports insertions in $\tilde O (N^{3/4})$
expected amortized time, where $\tilde O$ suppresses polylogarithmic terms.
This is the first result to achieve sublinear time insertions; previously it
was shown by Allen et al. that $\Theta(\sqrt{N})$ amortized combinatorial
changes per insertion could occur in the Voronoi diagram but a sublinear-time
algorithm was only presented for the special case of points in convex position.
