Group:Student Seminar
Title: Recent Progress on Computation Geometry
Speaker: Wei Yu University
Time: 2010-10-28 16:00-2010-10-28 17:00
Venue: FIT 1-222


In this talk I would like to cover a recent progress on computation geometry -- point location in 2D orthogonal regions in the RAM model. The data structure described in the paper uses O(n) space and provides O(loglog U) query time, where U is the size of the universe. This is optimal since a simpler problem, 1D predecessor search has a lower bound of Omega(loglog U) for linear space. Before this, it is believed that a lower bound of omega(loglog U) exists. So it is surprising that this result closes the gap for 2D point location in orthogonal regions on the upper bound side.  This result uses classical ideas like extensively built on previous developments in RAM model data structures like van Emde Boas tree. The idea used in the paper is clever but elementary, and it illustrates the tricks used in RAM model well.

Short Bio: