Speaker: Michael Kerber, MPII

Title: Semi-dynamic connectivity in the plane

Abstract:
---------
Motivated by a path planning problem we consider the following procedure.
Assume that we have two points $s$ and $t$ in the plane and take
$\cal K=\emptyset$.
At each step we add to $\cal K$ a compact convex set that does not
contain $s$ nor $t$.
The procedure terminates when the sets in $\cal K$ separate $s$ and $t$.
We show how to add one set to $\cal K$
in $O(1+k\alpha(n))$ amortized time plus the time needed
to find all sets of $\cal K$ intersecting the newly added set,
where $n$ is the cardinality of $\cal K$,
$k$ is the number of sets in $\cal K$ intersecting the newly added set, and
$\alpha(\cdot)$ is the inverse of the Ackermann function.
Available at http://arxiv.org/abs/1502.03690

Joint work with Sergio Cabello