CS 598 TMC, Fall 2021

Topics in Computational Geometry

Lecture Time and Link

Tue & Thu 11:00am-12:15pm on zoom

Instructor

Timothy Chan (tmc "at" illinois.edu)

office hours: Wednesdays at 2pm-3pm on zoom (email me if you want to meet at a different time, or meet in-person...)

Course Overview

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

Course Work

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

Resources

• Campuswire for Q&A and announcements (enrollment code: 6436)
• [BCKO] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications (3rd ed.), Springer-Verlag, 2008 (accessible online for UIUC students)
• [H-P] S. Har-Peled, Geometric Approximation Algorithms, AMS, 2011
• [Mat] J. Matousek, Lectures on Discrete Geometry, Springer, 2002
• [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

Lectures

(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 papers on fractional cascading]
• Sep 9: Preparata's trapezoid method. Persistent search trees. [Preparata's paper (1981) or PS, Sec 2.2.2.4; 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 2.2.2.3 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). [my paper; Matousek's paper]
• Oct 14: Approximate nearest neighbors. Grids and quadtrees. [H-P, Sec 11.2]
• Oct 19: Shifting. Balanced quadtrees. [Bern'93 and Lemma 3.3 in C.'98]
• Oct 21: Z-ordering. [C.'02 and C., Har-Peled, and Jones'18]
• Oct 26: Geometric approximation algorithms. Diameter. [my paper ('02)]
• Oct 28: Width. Coresets and epsilon-kernels. [Agarwal, Har-Peled, and Varadarajan's paper ('04) and survey]
• 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. Local search. [Smith and Wormald's paper, my paper with Sariel ('09)]
• Nov 16: TSP: Arora's PTAS. [Arora's journal paper and survey]
• Nov 18: Miscellaneous topics. Parametric search. [Megiddo's paper]
• 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