CS 598 TC, Spring 2017
Geometric Data Structures
Instructor:
Timothy Chan
(Siebel 3230, tmc "at" illinois.edu,
office hours: Wed 3:304:30 or by appointment)
Meeting Time and Place:
Wed & Fri 2:003: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.
 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, ...
Course Work:
 3 or 4 assignments (problem sets), worth 40%:
 presentation, worth 20%;
 a project that involves reading some papers and writing a report,
or alternatively doing some original research, worth 40%.
See guidelines for presentation and project.
Lectures:
[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...]
Jan 18, 20: 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)
Jan 25:
 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: digression on 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)
Jan 27, Feb 1:
 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
(O(n loglog n) space, O(loglog U) time;
see Sec 2 of paper)
Feb 3: Planar point location.
 The naive slab method (O(n^2) space, O(log n) time)
 The segment tree method (O(n log n) space, O(log^2 n) time; see Sec 10.3 of
BCKO)
 ... with fractional cascading (O(n log n) space, O(log n) time;
see Chazelle and Guibas' two
papers)
Feb 8:
 Preparata's trapezoid tree method (also O(n log n) space, O(log n) time;
see paper or Preparata and Shamos' old textbook)
 Persistent search tree method
(O(n log n) space, O(log n) time by path copying;
see Sarnak and Tarjan's
paper,
which also reduced space to O(n))
Feb 10:
 Planar separator method
(O(n) space, O(log n) time;
see Lipton and Tarjan's
paper)
 Random sampling method
(O(n) space, O(log n) time; see Clarkson and Shor's original paper or Mulmuley's book)
 Kirkpatrick's hierarchical triangulation method
(see paper, or Preparata and Shamos' book, or Iacono's video)
Feb 15:
 Point location in sublogarithmic time:
orthogonal case (O(n) space, O(loglog U) time;
see my paper from '11)
Feb 17:
 Point location in sublogarithmic time:
general case (O(n) space, O(log n/loglog n) or O(sqrt{log U/loglog U}) time;
see my '09 paper with Patrascu)
Feb 22, 24: Nonorthogonal range searching.
 Willard's method
(O(n) space, O(n^{0.793}) time in 2D, via the hamsandwich cut theorem;
see paper)
 A dual method (O(n^{4.82}) space, O(log n) time in 2D;
for duality, see Sec 8.2 of
BCKO)

Clarkson's cutting tree (O(n^{2+eps}) space, O(log n) time in 2D)
via the Cutting Lemma (proof by random sampling;
see
Clarkson's paper or Mulmuley's book)
Mar 1:

Matousek's partition tree (O(n) space, O(n^{1/2+eps}) time in 2D)
via the Partition Theorem (proof by iterative reweighting;
see
Matousek's paper or Mulmuley's book)

Time/space tradeoffs
Mar 3:

"Applications" to combinatorial geometry (SzemerediTrotter theorem
and Erdos' unit distance problem;
see Ch4 of
Matousek's book)
 Nonlinear range searching (via the linearization technique)
 Multilevel versions of partition trees
(see Sec 16.2 of BCKO)
Mar 8:
 Halfspace range reporting in 2D and 3D
(O(n log n) space, O(log n + k) time; see
my paper) via
the Shallow Cutting Lemma
(see Matousek's paper)
Mar 10: Dynamic geometric data structures. Dynamic 2D convex hull.
 Insertonly (O(log n) update and O(log n) query time, by
Preparata'79)
 Fully dynamic: the hull tree method
(O(log^2 n) update and O(log n) query time, by
Overmars and van Leeuwen'80; see also Preparata and Shamos' book)
Mar 15: General dynamization techniques.
 Static to insertonly:
The "logarithmic method" (Bentley and Saxe '80)
 Static to fully dynamic:
The "square root method" (same paper)
 Static to offline dynamic, via segment tree
Mar 17: Dynamic 2D point location
 Dynamic segment tree (O(log^2 n) query and update time)
 ... with dynamic fractional cascading (O(log n loglog n) query and O(log^2 n) update time)
 Sketch of a version of the latest method by
C. and Nekrich'15 (O(log n (loglog n)^2) query and O(log n loglog n) update time)