Geometric Data Structures

Instructor

Timothy Chan (Siebel 3230, tmc "at" illinois.edu, office hours: Wed 2:30-3:30 or by appointment)

Meeting Time and Place

Wed & Fri 11:00-11:15, Siebel 1103

Course Overview

This course is about data structures in computational geometry. We will discuss fundamental techniques and recent theoretical developments for a variety of basic geometric data structuring problems in a variety of models. Possible topics include:

• Orthogonal range searching: from basic methods (such as range trees) to current best results (such as my paper with Larsen and Patrascu)
• Point location: from standard solutions (segment trees, fractional cascading, persistence, planar separators, ...), to more recent sublogarithmic methods on the word RAM
• Nonorthogonal range searching: partition trees, cutting trees, random sampling, iterative reweighting, shallow cuttings
• Dynamic data structures: dynamic convex hull, dynamic point location, general dynamization techniques
• Approximate nearest neighbor searching: quadtrees, shifting, z-ordering, locality sensitive hashing
• Big data: external-memory geometric data structures, geometric streaming algorithms, ...

Prerequisite: a solid background in algorithm design and analysis (e.g., at the level of CS 374) is assumed.

Course Work

• 4 assignments (problem sets), worth 40%
• presentation, worth 20%
• a project (reading some papers and writing a report, or implementing some data structures, or doing some original research), worth 40%

(Assignments and projects may be done individually or in groups of 2.)

References

There is no required textbook, but you may find the following general references useful:

Lectures

(I'll provide copies of my handwritten notes, and links to relevant papers, below...)

Aug 28, 30, Sep 4: Introduction. Orthogonal range searching.

• k-d trees (O(n) space, O(n^{1-1/d} + k) time; see Sec 5.2 of BCKO)
• Priority search trees and Cartesian trees for 2D 3-sided emptiness/reporting (O(n) space, O(log n + k) time; see Sec 10.2 of BCKO and wikipedia page)
• Range trees (O(n log^{d-1} n) space, O(log^{d-1} n) time; see Sec 5.3-5.6 of BCKO)
• my notes

Sep 6, 11:

• Improving space by bit packing: Chazelle'88 for 2D counting (O(n) space, O(log n) time; see Sec 3.1 of paper)
• Improving time: warm-up with 1D predecessor search
• van Emde Boas trees (O(n) space, O(loglog U) time; see wikipedia, or the Cormen et al. textbook, 3rd ed.)
• fusion trees (O(n) space, O(log_w n) time, but rough sketch only; see Fredman and Willard's paper)
• my notes

Sep 11, 13:

• Improving time in 2D (O(n log n) space, O(loglog U) time (for emptiness))
• Improving time and space in 2D: Alstrup, Brodal, and Rauhe's grid-based method (O(n loglog U) space, O((loglog U)^2) time; see paper [Sec 3])...
• Improving time and space in 2D: C.-Larsen-Patrascu'11...