
\(V_{i..n}\) : the standard Voronoi diagram of \(n\)  sites has \(O(n)\)  combinatorial complexity. It can be initially computed in \(O(n\log n)\)  time (e.g., see [1]}, [2]}). It can be updated after the removal of a site in \(O(n)\)  time [3]}.

\(\cup B_{1..i}\) : the union of \(n\)  disks also has \(O(n)\)  combinatorial complexity [4]}, [5]}. To compute \(\cup B_{1..i}\)  from \(\cup B_{1..i-1}\) , a new disk can be added to the union in \(O(n\log n)\)  time, e.g., with a typical plane sweep algorithm.

\(\hat{V}_{i..n}\) : since \(\cup B_{1..i-1}\)  has \(O(n)\)  complexity, and the boundary of \(B^*(s_i)\)  can only intersect each edge of \(\cup B_{1..i-1}\)  twice, \(\hat{B}(s_i)\)  also has \(O(n)\)  complexity. Given that both \(\hat{B}(s_i)\)  and \(V_{i..n}\)  have \(O(n)\)  combinatorial complexity, \(\hat{V}_{i..n}\)  has \(O(n^2)\)  combinatorial complexity. The diagram \(\hat{V}_{i..n}\)  can be computed in \(O(n^2\log n)\)  time, e.g., with a typical plane sweep algorithm.

\(D_i\) : we do not maintain the faces of the diagram \(D_i\)  explicitly as ordered sequences of edges. Instead, for each site \(s\) , we simply maintain the region \(D_i(s)\)  as the (unordered) set of edges \(\cup _{1\le j\le i}\;edges(\hat{V}_{j..n}(s))\) .
That is, at each iteration \(i\) , we add to the edge set of each site \(s\)  the edges bounding the (possibly empty) region of \(s\)  in \(\hat{V}_{i..n}\) . Note that after iteration \(j\) , the set of edges of \(s_j\)  does not change anymore. Since \(\hat{V}_{i..n}\)  has \(O(n^2)\)  complexity for any \(i\) , the collective size of the these edge sets is \(O(n^3)\)  throughout the algorithm.

