Incremental Voronoi diagrams (Q1688855)

In the paper the authors study the construction of Voronoi diagrams using the flarb operation. The idea of the flarb operation is the following: given a simple closed curve \(C\) in the plane whose interior intersects a \(3\)-regular embedded plane graph \(G\) in a connected component, split both \(C\) and all the edges that it crosses at the point of intersection, remove every edge and vertex that lies in the interior of \(C\), and add each curve in the subdivision of \(C\) as a new edge. The flarb operation can be used to represent the insertion of new cells in different types of Voronoi diagrams. The study starts with the proof that the amortized cost (the minimum number of links (edge insertions) and cuts (edge removals) needed to perform the operation) of the flarb operation is \(O(\sqrt{n})\), where \(n\) is the number of vertices in the graph. Moreover, the authors show that some sequences of flarbs require \(\Omega(\sqrt{n})\) links and cuts per flarb. After proving the bounds of the flarb operation, the authors present an output-sensitive data structure that maintains the nearest- and farthest-point Voronoi diagram of a set \(S\) of \(n\) sites in convex position as new sites are added to \(S\). Upon an insertion, the proposed data structure finds the minimum number \(K\) of edge insertions and deletions necessary to update the Voronoi diagram of \(S\). The running time of each insertion is \(O(K \log^7 n)\), where the amortized value of \(K\) is \(O(\sqrt{n})\) if arbitrary insertions are allowed while maintaining convex position, and \(O(\log n)\) if sites are added in clockwise order. The interesting features of the proposed data structure are that it explicitly maintains the graph structure of the Voronoi diagram after every insertion, and that it maintains the Voronoi diagram in a grappa tree.