Abstract: The Voronoi diagram (VD) is a fundamental geometric structure in many applications. There are fast and simple algorithms to construct the VD of static point sets. For complex sites (i.e., other than points) the algorithms are more sophisticated, and a few efficient solutions exist. However, updating the VD of dynamic sites is still challenging, and efficient solutions exist only for points. We propose an algorithm for constructing and updating the VD of large dynamic sets of complex sites. Although existing incremental algorithms allow fast insertion of complex sites, this work presents the first efficient implementation of the removal operation.