Updating an abstract Voronoi diagram in linear time, after deletion of one site , has been an open problemfor a long time. 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  . We introduce the concept of a Voronoi-like diagram, a relaxed version of a Voronoi construct that has a structure similar to an abstract Voronoi diagram, without however being one. Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible. We formalize the concept  and prove that it is robust under an insertionoperation, thus ,  enabling its use in incremental constructions  .
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 .
D
in linear time,
R
, has been an open problemfor a long time. Similarly for various
in linear time has been a well-known open problem; similarly, for
R
generalized sites, other than points
non-point sites
R
we present a simple,
, we present an
A
of one site
R
a
an abstract
R
abstract
ordinary
R
however
, however,
D
Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute, thus, making an expected linear-time construction possible.
A
,
R
an insertionoperation, thus
insertion
A
therefore,
A
. 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