**F. Aurenhammer and O. Schwarzkopf**

We present a simple algorithm for maintaining order- Voronoi diagrams in the
plane. By using a duality transform that is of interest in its own right, we
show that the insertion or deletion of a site involves little more than the
construction of a single convex hull in three-space. In particular, the
order- Voronoi diagram for sites can be computed in time
and optimal space by an on-line
randomized incremental algorithm. The time bound can be improved by a
logarithmic factor without losing much simplicity. For
,
this is optimal for a randomized incremental construction; we show that the
expected number of structural changes during the construction is
. Finally, by going back to primal space, we obtain a dynamic data
structure that supports -nearest neighbor queries, insertions, and
deletions in a planar set of sites. The structure promises easy
implementation, exhibits a satisfactory expected performance, and occupies no
more storage than the current order- Voronoi diagram.