Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Semi-dynamic connectivity in the plane
Speaker:Michael Kerber
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 14 April 2015
Duration:30 Minutes
Building:E1 4
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.
Name(s):Michael Kerber
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Michael Kerber, 04/01/2015 03:21 PM
Last modified:
Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Michael Kerber, 04/01/2015 03:21 PM -- Created document.