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.)


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: