Deletion in Abstract Voronoi Diagrams in Expected Linear Time

Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been a long standing open problem. Similarly for various concrete Voronoi diagrams of generalized sites, other than points. In this paper we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion. To this aim, we introduce the concept of a \emph{Voronoi-like diagram}, a relaxed version of a Voronoi construct, that has a structure similar to an abstract Voronoi diagram, without however being one. We use Voronoi-like subdivisions as intermediate structures, which are much simpler to compute, thus, making an expected linear-time construction possible. We formalize the concept and prove that it is robust under an \emph{insertion} operation, thus, enabling its use in (randomized) incremental constructions.