CS 598 TMC, Fall 2021
Topics in Computational Geometry
Lecture Time and Link
Tue & Thu 11:00am-12:15pm on zoom
(tmc "at" illinois.edu)
office hours: Wednesdays at 2pm-3pm
(email me if you want to meet at a different time, or meet in-person...)
Computational geometry is about the design and analysis of
efficient algorithms for solving problems
that involve geometric data or geometric objects.
This course will cover selected topics in the area that I find theoretically
interesting (occasionally touching on recent research).
No prior knowledge in computational geometry is assumed -- the only prequisite
is a solid background in (and a love of) algorithms at the level of CS374 or equivalent.
(But if you have taken Jeff's CS498 course last year, this course will be a good continuation, as the overlap of topics will be minimal.)
Possible topics include
geometric data structures (e.g., orthogonal range searching,
point location, nonorthogonal range searching),
approximate nearest neighbor search and related problems,
geometric approximation algorithms (e.g., independent set, set cover,
traveling salesman), and
combinatorial geometry (e.g., incidences, k-sets, Davenport-Schinzel sequences).
Along the way, we will encounter many fun solutions and techniques
(k-d trees, range trees, segment trees, fractional cascading,
persistence, planar separators, random sampling, randomized incremental construction,
cutting lemma, partition theorem, parametric search,
quadtrees, Z-ordering, core sets, epsilon-nets, multiplicative
weight update, local search, ...).
- 4 homeworks (problem sets), worth 50%
- HW1 (due Sep 24 Fri 5pm)
- HW2 (due Oct 20 Wed 5pm)
- HW3 (due Nov 10 Wed 5pm)
- HW4 (due Dec 8 Wed 5pm)
- submit homework on Gradescope
(entry code JBD2G7)
- presentation, worth 15%
- a project (reading some papers and writing a report,
or doing some original research), worth 35%
See guidelines for presentation and project.
- Campuswire for Q&A and announcements
(enrollment code: 6436)
[BCKO] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars,
Geometry: Algorithms and Applications (3rd ed.),
Springer-Verlag, 2008 (accessible online for UIUC students)
[H-P] S. Har-Peled,
Geometric Approximation Algorithms,
[Mat] J. Matousek,
Lectures on Discrete Geometry,
[PS] F. P. Preparata and M. I. Shamos,
Computational Geometry: An Introduction, Springer, 1985
[GRT] J. Goodman, J. O'Rourke, and C. D. Toth (eds.),
Handbook of Discrete and Computational Geometry (3rd ed.),
CRC Press, 2017
(Scribbles from class, and links to relevant papers, will be provided below.
For registered students, recordings of the zoom lectures may be accessed at mediaspace.)
- Aug 24: Introduction. Orthogonal range searching.
k-d trees. [BKCO, Sec 5.2]
- Aug 26: Range trees.
[BKCO, Sec 5.3-5.6; or PS, Sec 2.3.4; also, Chazelle'88 (Sec 3.1)]
- Aug 31: Alstrup, Brodal and Rauhe's recursive grid method. [Alstrup et al.'s paper (FOCS'00), Sec 3]
- Sep 2: Final remarks on orthogonal range searching.
Planar point location.
[C., Larsen, and Patrascu (SoCG'11)]
- Sep 7: Segment trees + fractional cascading.
[BKCO, Sec 10.3; Chazelle and Guibas' two
on fractional cascading]
- Sep 9: Preparata's trapezoid method. Persistent search trees.
[Preparata's paper (1981) or PS, Sec 188.8.131.52; Sarnak and Tarjan's paper (1986)]
- Sep 14: Planar separators. Kirkpatrick's hierarchical method.
[Lipton and Tarjan's paper ('80);
Kirkpatrick's paper ('83) or PS, Sec 184.108.40.206 or John Iacono's video)]
- Sep 16: Random sampling. Randomized incremental construction.
[Clarkson and Shor's original paper or Mulmuley's book (in library) or BKCO, Sec 6.2]
- Sep 21: Point location in sublogarithmic time: orthogonal case. [my paper (SODA'11)]
- Sep 23: Point location in sublogarithmic time: non-orthogonal case. [my '09 paper with Patrascu]
- Sep 28: Nonorthogonal range searching.
Willard's method (via ham-sandwich cuts). Duality.
[Willard's old paper;
BKCO, Sec 8.2 on duality]
- Sep 30: Clarkson's cutting tree (proof by random sampling). Matousek's partition tree.
[Clarkson's paper or Mulmuley's book]
- Oct 5: Proof of the partition theorem (by multiplicative weight update).
[Matousek's paper or Mulmuley's book]
- Oct 7: Applications to combinatorial geometry, nonlinear range searching, and
multi-level variants. [Mat, Ch4; BKCO, Sec 16.2]
- Oct 12: Halfspace range reporting (via shallow cuttings).
- Oct 14: Approximate nearest neighbors.
Grids and quadtrees. [H-P, Sec 11.2]
- Oct 19: Shifting. Balanced quadtrees.
and Lemma 3.3 in C.'98]
- Oct 21: Z-ordering.
C., Har-Peled, and Jones'18]
- Oct 26: Geometric approximation algorithms.
[my paper ('02)]
- Oct 28: Width. Coresets and epsilon-kernels.
[Agarwal, Har-Peled, and Varadarajan's
- Nov 2: Algorithms for epsilon-kernels.
[Sec 2 of my paper ('06)]
- Nov 4: Geometric independent set: greedy (for arbitrary squares/disks), shifted grid (for unit squares/disks). [Hochbaum and Maass'85]
- Nov 9: Shifted quadtree (for arbitrary squares/disks).
[my paper ('01)]
- Nov 11: Geometric separator theorems.
[Smith and Wormald's paper, my paper with Sariel ('09)]
- Nov 16: TSP: Arora's PTAS.
journal paper and survey]
- Nov 18: Miscellaneous topics. Parametric search.
- Nov 23 and 25: Break.
- Nov 30: Randomized alternative to parametric search.
[my technique ('98)]
- Dec 2: dynamic 2D convex hull.
[Overmars and van Leeuwen'80 or Sec 3.3.6 of PS; my paper ('99)]
- Dec 7: student presentations