[Mittagsseminar TI] Fwd: [all] Einladung zur Verteidigung meiner Bachelorarbeit

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

Tomorrow.


-------- Forwarded Message --------
Subject: [all] Einladung zur Verteidigung meiner Bachelorarbeit
Date: Mon, 27 Nov 2017 13:28:10 +0100
From: Christian Hofer <hoferch91@zedat.fu-berlin.de>
To: all@mi.fu-berlin.de
CC: mulzer@inf.fu-berlin.de

Liebe Institutsangehörige,

hiermit möchte ich Sie herzlich zur Verteidigung meiner Bachelorarbeit mit
dem Titel "Fast dynamic planar convex set maintenance using finger trees"
einladen. Die Verteidigung findet am Dienstag, 5. Dezember, um 12:15 Uhr
in der Arnimallee 3, SR 130 statt. Betreut wurde die Arbeit von Prof. Dr.
Wolfgang Mulzer.

Abstract:
Let a convex set in the plane be given by either a set of points or
half-spaces. The maintenance of it under insertion and deletion of
elements is a fundamental problem in computational geometry. This thesis
considers a data-structure which solves this problem. It was drafted by
the researchers Kaplan, Tarjan and Tsioutsiouliklis in a paper about
kinetic heaps (priority queues with linear functions as keys rather than
fixed values). However it was never written down in detail. We state their
construction explicitly. Its foundation is built by a deletion-only
structure which uses finger trees (height balanced trees with preferred
access points) to represent convex sets. With the semi-dynamic structure
at hand, a fully dynamic one may be constructed using given dynamization
transformations. The binary counting scheme transformation of Bentley and
Saxe yields an insertion-and-deletion structure with $O(\log^2 n)$
worst-case vertical ray query time, $O(\log n)$ amortized insertion time
and $O(\log n \log \log n)$ amortized deletion time. A transformation of
Brodal and Jacob results in a structure with $O(\log n)$ worst-case
vertical ray query time, $O(\log n \log \log \log n)$ amortized insertion
and $O(\log n \log \log n)$ amortized deletion time.

Viele Grüße,


Chris Hofer

_______________________________________________
Automatischer Mailverteiler an Gruppe 'ml-all-mi'.
Hinweise dazu siehe Hilfeseite:
https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature