Max-Planck-Institut für Informatik
max planck institut
informatik
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:Point Location in Dynamic Planar Subdivisions
Speaker:Eunjin Oh
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 27 March 2018
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Eunjin Oh
Phone:068193251017
EMail:eunjin9951@gmail.com
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
Created:
Eunjin Oh, 03/14/2018 02:03 PM
Last modified:
Uwe Brahm/MPII/DE, 03/27/2018 04:01 AM
  • Eunjin Oh, 03/14/2018 02:03 PM -- Created document.