6.851: Advanced Data Structures (Spring'14)

First, we'll finish our coverage of fractional cascading from Lecture 3 by illustrating a really cool application: 3D orthogonal range searching in O(log n) time. This gives us the second log factor improvement mentioned in Lecture 3, giving O(log^d−2 n) for d dimensions.

Second, we'll cover a style of data structures for moving data, e.g., where 2D points move at known velocity and acceleration. Although the main study here is in 2D (and 3D), we'll focus on two 1D problems that are well-understood and fit in a lecture: kinetic predecessor and kinetic priority queues.