[+] Geometric: O(log n) 3D orthogonal range searching via fractional cascading; kinetic data structures  
In this lecture, we continue (and finish) the theme of geometric
data structures.
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 wellunderstood and fit in a lecture: kinetic predecessor and kinetic priority queues.  
Lecture notes, page 1/8 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/8 • [previous page] • [next page] • [PDF] 

The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.