Center for Algorithms and Theory of Computation

CS 269S, Winter 2018: Theory Seminar
Bren Hall, Room 1423, 1pm


March 16, 2018:

Towards an Optimal Method for Dynamic Planar Point Location

Martha Osegueda

In this paper, we study the linear space structure necessary to perform planar point location for connected planar subdivisions in near-logarithmic query and update time. The paper is decomposed into non-recursive and recursive descriptions. Due to the paper's length and density we will only explore the non-recursive description which details the process of building a linear-space multi-colored segment tree that achieves $O(\log n(\log\log n)^2)$ query time and $O(\log n\log\log n)$ update time.

(Based on a paper by T. Chan and Y. Nekrich from FOCS 2015.)