Evanthia Papadopoulou: Deletion in abstract Voronoi diagrams
in expected linear time
Abstract:
Updating an abstract Voronoi diagram in linear time, after deletion of
one site, has been an open problem for a long time. Similarly for
various concrete Voronoi diagrams of generalized sites, other than
points. In this talk I will present a simple, expected linear-time
algorithm to update an abstract Voronoi diagram after deletion. To this
goal, I will 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.
Joint work with Kolja Junginger