AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

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 $\calK=\emptyset$. At each step we add to $\calK$ a compact convex set that does not contain $s$ nor $t$. The procedure terminates when the sets in $\calK$ separate $s$ and $t$. We show how to add one set to $\calK$ in $O(1+k\alpha(n))$ amortized time plus the time needed to find all sets of $\calK$ intersecting the newly added set, where $n$ is the cardinality of $\calK$, $k$ is the number of sets in $\calK$ intersecting the newly added set, and $\alpha(\cdot)$ is the inverse of the Ackermann function.

Michael Kerber

--email hidden

passcode not visible

logged in users only