CS 269S, Fall 2011: Theory Seminar
DBH 1433
4 November 2011:

Speaker: Joseph Simons

Title: Dynamic Point Location with Sub-Logarithmic Local Updates

Presenting ongoing work with Maarten and Darren.

Abstract: We consider the problem of dynamic point location among imprecision regions. That is, we are given a set of n points whose location we only know approximately, and we maintain a set of n regions whose size depends on the precision of the corresponding point. We support point location queries among these regions and insertions and deletions of regions in O(log n) time. We also support local updates to re-size or move a region in sub-logarithmic time.