Campus Event Calendar
Event Entry
What and Who
Point Location in Dynamic Planar Subdivisions
Eunjin Oh
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 27 March 2018
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We study the point location problem on dynamic planar subdivisions that allows insertions and deletions of edges. In our problem, the underlying graph of a subdivision is not necessarily connected. We present a data structure of linear size for such a dynamic planar subdivision that supports sublinear-time update and polylogarithmic-time query. When only deletions of edges are allowed, the update time and query time are just O(\alpha(n)) and O(log n), respectively.
Contact
Eunjin Oh
068193251017
--email hidden
passcode not visible
logged in users only
Eunjin Oh, 03/14/2018 14:03 -- Created document.