6.851: Advanced Data Structures (Spring'12)

Prof. Erik Demaine     TAs: Tom Morgan, Justin Zhang


[Home] [Lectures] [Assignments] [Project] [Problem Session]

Lecture 4 Video     [previous] [next]

[+] Geometric: O(log n) 3D orthogonal range searching via fractional cascading; kinetic data structures Scribe Notes [src]
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(logd−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.

Download Video: 360p, 720p

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.