Dynamic construction of abstract Voronoi diagrams

The abstract Voronoi diagram (AVD) introduced by R. Klein is a generalization of various concrete Voronoi diagrams—data structures actively used in the last decades for solving theoretical and practical geometric problems. This paper presents a fully dynamic algorithm for AVD construction based on Klein's incremental approach. It needs $O(n)$ worst\df case time for a new site insertion in an AVD with $n$ sites. For the first time a possibility of effective site deletion without full reconstruction of AVD is proved. The proposed method for site deletion requires $O(mn)$ expected time where $m$ is the number of invisible sites, and $O(n)$ if invisible sites are not allowed. The dynamic algorithm consumes $O(n)$ memory at any moment.