  Updating an abstract Voronoi diagram after deletion of one site in linear
time has been a well-known open problem; similarly, for concrete Voronoi
diagrams of non-point sites. In this paper, we present an expected linear-time
algorithm to update an abstract Voronoi diagram after deletion of one site. We
introduce the concept of a Voronoi-like diagram, a relaxed version of an
abstract Voronoi construct that has a structure similar to an ordinary Voronoi
diagram, without, however, being one. We formalize the concept, and prove that
it is robust under insertion, therefore, enabling its use in incremental
constructions. The time-complexity analysis of the resulting simple randomized
incremental construction is non-standard, and interesting in its own right,
because the intermediate Voronoi-like structures are order-dependent. We
further extend the approach to compute the following structures in expected
linear time: the order-(k+1) subdivision within an order-k Voronoi region, and
the farthest abstract Voronoi diagram after the order of its regions at
infinity is known.
