CS 598 TMC, Fall 2019
Geometric Data Structures
Instructor
Timothy Chan
(Siebel 3230, tmc "at" illinois.edu,
office hours: Wed 2:303:30 or by appointment)
Meeting Time and Place
Wed & Fri 11:0011: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, zordering, locality sensitive hashing
 Big data:
externalmemory 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:

[BCKO] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars,
Computational
Geometry: Algorithms and Applications (3rd ed.),
SpringerVerlag, 2008

[GRT] J. Goodman, J. O'Rourke, and C. D. Toth (eds.),
Handbook of Discrete and Computational Geometry (3rd ed.),
CRC Press, 2017
Lectures
(I'll provide copies of my handwritten notes, and links to relevant papers, below...)
Aug 28, 30, Sep 4: Introduction. Orthogonal range searching.
 kd trees (O(n) space, O(n^{11/d} + k) time;
see Sec 5.2 of BCKO)
 Priority search trees and Cartesian trees for 2D 3sided emptiness/reporting (O(n) space, O(log n + k) time; see Sec 10.2 of BCKO
and wikipedia page)
 Range trees (O(n log^{d1} n) space, O(log^{d1} n) time; see Sec 5.35.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: warmup 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 gridbased method (O(n loglog U)
space, O((loglog U)^2) time; see
paper [Sec 3])...
 Improving time and space in 2D: C.LarsenPatrascu'11...