CS 269S, Spring 2013: Theory Seminar
Bren Hall, Room 1420, 1pm
May 3, 2013:

Dynamic Planar Point Location with Sub-Logarithmic Local Updates

by Maarten Löer, Joe Simons, Darren Strash

Presented by Joe Simons

We study planar point location in a collection of disjoint fat regions, and investigate the complexity of local updates: replacing any region by a different region that is "similar" to the original region. (i.e., the size differs by at most a constant factor, and distance between the two regions is a constant times that size). We show that it is possible to create a linear size data structure that allows for insertions, deletions, and queries in logarithmic time, and allows for local updates in sub-logarithmic time on a pointer machine.