CS 598 TC, Spring 2017

Geometric Data Structures


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

Meeting Time and Place:

Wed & Fri 2:00-3:15, Siebel 1109

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. Prior knowledge in computational geometry is not required, but students are assumed to have a solid background in algorithm design and analysis.

The following is a list of possible topics.

Course Work:

See guidelines for presentation and project.


[I'll provide links to relevant papers below. There is no required textbook, although de Berg, Cheong, van Kreveld, and Overmars's book is a useful starting point for the less recent topics. See also the newest 2017 edition of the CRC Handbook...]

Jan 18, 20: Introduction. Orthogonal range searching.

Jan 25:

Jan 27, Feb 1:

Feb 3: Planar point location.

Feb 8:

Feb 10:

Feb 15:

Feb 17:

Feb 22, 24: Nonorthogonal range searching.

Mar 1:

Mar 3:

Mar 8:

Mar 10: Dynamic geometric data structures. Dynamic 2D convex hull.

Mar 15: General dynamization techniques.

Mar 17: Dynamic 2D point location.

Mar 29, 31: Approximate nearest neighbor search. In constant dimensions.

Apr 5, 7, 12: In high dimensions.

  • Apr 14, 19: Big data. External-memory and cache-oblivious data structures.
  • Apr 21: Streaming (insert-only).
  • Apr 26: Streaming (dynamic).

  • Apr 28: Student presentations.
  • May 3: Student presentations.