CS 498 TC, Fall 2024: Computational Geometry

CS 498 TC, Fall 2024:

Computational Geometry

Instructor

Timothy Chan (tmc "at" illinois.edu, office hours: Tuesdays 1:30-2:30pm (note the change!) (or by appointment), Siebel 3230)

Meeting Time/Place

Tue & Thu 3:30-4:45pm, Lu MEB 3101

Course Work

5 Homeworks
- HW1 (due Sep 18 Wed 5pm) (9/15: fixed number of points in Q2) [solutions (use this link for TC3 or this link for TC4)]
- HW2 (due Oct 2 Wed 5pm) [solutions (use this link for TC3 or this link for TC4)]
- HW3 (due Oct 30 Wed 5pm) [solutions (use this link for TC3 or this link for TC4)]
- HW4 (due Nov 13 Wed 5pm) [solutions (use this link for TC3 or this link for TC4)]
- HW5 (due Dec 4 Wed 5pm) [solutions (use this link for TC3 or this link for TC4)]
Midterm (October 7 Monday 7pm-9pm, Siebel 2405)
- exam (use this link for TC3 or this link for TC4)
- solutions (use this link for TC3 or this link for TC4)
- Covers everything up to and including Oct 1's lecture.
- You may bring one double-sided 8.5"x11" cheat sheet, with your name and NetID written on the upper right corner. (Two single-sided sheets are okay.) The sheet should be handwritten by you (not photocopied or printed). We may not return your cheat sheet, so if you want to keep a copy, you should photocopy your sheet before the exam.
- No other material is allowed.
- I'll have extra office hours on Oct 4 Friday at 4:00-5:00 and Oct 7 Monday at 2:00-3:00. (My office hour on Oct 8 Tuesday will be cancelled.)
- Here is a sample past midterm (use this link for TC3 or this link for TC4; solutions are not provided, but feel free to ask me questions, e.g., during office hours).
- Do not discuss the content of the exam with others (in person or online) for 24 hours, till all conflict exams have been completed.
Final Exam (December 16 Monday 1:30pm-4:30pm, Lu MEB 3101)
- The exam is comprehensive (covers everything, though with a little more emphasis on post-midterm material).
- You may bring two double-sided 8.5"x11" cheat sheets, with your name and NetID written on the upper right corner. (Four single-sided sheets are okay.) The sheets should be handwritten by you (not photocopied or printed). We may not return your cheat sheets, so if you want to keep a copy, you should photocopy your sheets before the exam.
- No other material is allowed.
- I'll have extra office hours on Dec 12 Thursday at 3:30pm-4:30pm and Dec 13 Friday at 2pm-3pm.
- Here is a sample past final (use this link for TC3 or this link for TC4; solutions are not provided, but feel free to ask me questions, e.g., during office hours) (note: in Q3, Klee's measure problem refers to computing the area of a union of n axis-aligned rectangles in 2D, which can be solved in O(n log n) time).
- If you require a conflict exam (due to one of the official reasons stated in the student code) or special arrangements with DRES, you should email me (tmc) ASAP.
For grad students taking the 4-credit version, there is also a presentation of a research paper; see presentation guidelines.

Administrivia

Course Policies
Gradescope (entry code 5KDE47)
Ed (for announcements and Q&A)

Course Overview

We will study efficient algorithms for a variety of fundamental geometric problems: convex hulls, Voronoi diagrams/Delaunay triangulations, low-dimensional linear programming, line segment intersection, polygon triangulation, geometric shortest paths, visibility, etc. Computational geometry has applications to many areas (geometric data are everywhere), although the focus of the course is on theoretical results and techniques (we will encounter lots of cool algorithmic ideas, including divide-and-conquer, prune-and-search, randomization, plane sweep, etc.). A solid background in algorithm design and analysis is assumed (at the level of CS374).

References

There is no required textbook, but you may find the following useful (all accessible online for UIUC students):

[BCKO] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications (3rd ed.), Springer-Verlag, 2008
[PS] F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 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 book chapters or papers, will be provided below. For registered students, lecture recordings may be accessed on mediaspace.)

Aug 27: Introduction. Convex hull in 2D.
Aug 29: Jarvis march (O(n^2)). Graham's scan (O(n log n)). [Ref: Ch3 of PS]
Sep 3 and Sep 5: Timothy will be away, but here are links to pre-recorded lectures (or this for TC3 or this for TC4 -- these recordings have also been uploaded to mediaspace) on: mergehull, lower bounds, and applications of convex hulls and duality. [Refs: Ch3 of PS; Ben-Or's paper]
Sep 10: Output-sensitive O(n log h) algorithms (by divide-prune-and-conquer, or by grouping). [Refs: C., Snoeyink, and Yap (Sec 3) and my other paper (Sec 2)]
Sep 12: Convex hull in 3D.
Sep 17: Combinatorics/representations of convex polyhedra. Gift-wrapping (O(nh)). [Ref: Ch 3.4.1 of PS]
Sep 19: Randomized incremental (O(n log n)). [Ref: Ch 11 of BCKO]
Sep 24: Divide-and-conquer (O(n log n)). [Refs: my write-up on the kinetic interpretation; my implementations in C++: "brute force", gift-wrapping and divide-and-conquer; see also qhull and CGAL]
Sep 26 and Oct 1: Voronoi diagrams and Delaunay triangulations. [Refs: Ch 5 of PS; some interactive tools on Voronoi diagrams and Delaunay triangulations; Ch7 of BCKO describes Fortune's sweep algorithm (a demo of Fortune's algorithm from Desmos) and Ch 9 of BCKO describes a randomized incremental algorithm]
Oct 3: Applications of Voronoi/Delaunay.
Oct 8: No lecture (because midterm is on Oct 7 Monday).
Oct 10: Applications of Voronoi/Delaunay. [Ref: Sec 9.1 and Thm 9.8 of BCKO]
Oct 15: Linear programming.
Oct 17: Megiddo/Dyer's prune-and-search algorithm. [Ref: Ch 7.2.5 of PS]
Oct 22: Seidel's randomized incremental algorithm and Clarkson's random sampling algorithm. [Ref: Ch4 of BCKO (on Seidel); Ch 9 of Motwani and Raghavan's book on randomized algorithms]
Oct 24: Arrangement of lines. Incremental algorithm and the zone theorem. [Ref: Ch 8 of BCKO]
Oct 29: Intersections of line segments. Bentley-Ottmann sweep. [Ref: Ch2 of BCKO, Chazelle and Edelsbrunner's paper (not easy to read!)]
Oct 31: Balaban's divide-and-conquer. Point location. The slab method. [Ref: Balaban's paper]
Nov 5: Segment trees. Persistent search trees. [Ref: Ch 2 of PS, Sarnak and Tarjan's paper]
Nov 7: Randomized incremental. Kirkpatrick's hierarchy. [Refs: Ch 6 of BCKO, Ch 2.2 of PS]
Nov 12 and Nov 14: Polygon triangulation. Application to art gallery. [Refs: Ch3 of BCKO; Seidel's O(n log* n) randomized algorithm or Chazelle's linear-time algorithm (complicated!)]
Nov 19: Application to motion planning (Minkowski sum, union complexity). [Ref: Ch13]
Nov 21: Orthogonal range searching. k-d trees and range trees. [Ref: Ch 5 of BCKO]
Nov 25-29: Thanksgiving break.
Dec 3 and Dec 5: Non-orthogonal (triangle) range searching... [Ref: Ch16 of BCKO; Agarwal and Erickson's survey]
Dec 10: grad student presentations (se this link for TC3 or this link for TC4)