Speaker: Haim Kaplan (TAU)

Title: Dynamic maintenance of convex hulls in three dimensions 
and of weighted Voronoi diagrams in the plane

Abstract:
---------
We revisit Chan's algorithm for efficiently maintaining the
lower envelope of a set of planes in $\reals^3$ (or, dually, the
convex hull of a set of points in three dimensions), under
insertions and deletions of planes. We present
a variant of his technique that uses a single binary counter, with a
simpler analysis and improved performance.
Specifically, our scheme uses $O(n)$ space, supports an insertion in
amortized $O(\log^3 n)$ time,
a deletion in amortized $O(\log^5n)$ time, and a query in
worst-case $O(\log^2 n)$ time.

We then extend the technique to the efficient maintenance of the
lower envelope of a collection of bivariate algebraic functions
of constant description complexity.
In particular, we obtain an algorithm that dynamically
maintains several kinds of
Voronoi diagrams of planar sites, under insertions and deletions,
and queries (each seeking the nearest site to a query point),
for which the
sites are simply shaped objects, and the static diagram has
linear complexity.
We can support both updates and queries in polylogarithmic time,
thereby improving
earlier results of Agarwal, Efrat and Sharir.

This technique  depends on the existence (and
efficient construction) of \emph{``vertical'' shallow cuttings},
in arrangements of planes or of more general surfaces in $\reals^3$,
consisting of semi-unbounded vertical (pseudo-)prisms.
For planes, an efficient deterministic construction of such cuttings
was recently given by
Chan and Tsakalidis. Consequently,
a large portion of our study of the case of general surfaces
is devoted to the construction of vertical shallow cuttings of this kind,
for bivariate algebraic functions. Furthermore,
the ceilings of the prisms of our shallow cutting
for level $k$ in the arrangement of the function graphs
form a terrain, that lies above level $k$  and each of
its prisms intersects at most
$(1+\eps)k$ function graphs, for any desired accuracy parameter $\eps$.

The problems studied in this paper have many applications, and our results
lead to improved bounds for them. We also introduce new applications, where
we show how to use our general dynamic nearest neighbor results for
the  efficient dynamic maintenance of connectivity in
disk graphs and an efficient construction of spanners in disk graphs.

Joint work with Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir