CS 598 TMC, Fall 2019

Geometric Data Structures


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:

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

Course Work

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

See guidelines for presentation and project.


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


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

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

Sep 6, 11:

Sep 11, 13, 18:

Sep 18, 20: Planar point location.

Sep 25:

Sep 27:

Oct 2:

Oct 4:

Oct 9, 11: Nonorthogonal range searching.

Oct 16, 18:

Oct 23:

Oct 25: Dynamic geometric data structures. Dynamic 2D convex hull.

Oct 30: General dynamization techniques.

Nov 1: Dynamic 2D point location.

Nov 6, 8: Approximate nearest neighbor search. In constant dimensions.

Nov 13, 15: In high dimensions.

Nov 20:

Nov 22:

Dec 4: Wrap-up. Orthogonal range searching in moderate dimensions.

Dec 7, 11: Student presentation.