CS 498 TC, Fall 2024:
Computational Geometry
Instructor
Timothy Chan
(tmc "at" illinois.edu, office hours: Tuesdays 1:302:30pm (note the change!) (or by appointment), Siebel 3230)
Meeting Time/Place
Tue & Thu 3:304:45pm, Lu MEB 3101
Course Work
 5 Homeworks
 Midterm (October 7 Monday 7pm9pm, 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 doublesided 8.5"x11"
cheat sheet, with your name and NetID written on the upper right corner. (Two singlesided 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:005:00 and Oct 7 Monday at 2:003: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
 For grad students taking the 4credit version, there is also
a presentation of a research paper; see presentation guidelines.
Administrivia
Course Overview
We will study efficient algorithms for a variety of fundamental geometric problems: convex hulls, Voronoi diagrams/Delaunay triangulations, lowdimensional 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 divideandconquer, pruneandsearch, 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.),
SpringerVerlag, 2008

[PS] F. P. Preparata and M. I. Shamos,
Computational Geometry: An Introduction,
SpringerVerlag, 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 prerecorded 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; BenOr's paper]

Sep 10: Outputsensitive O(n log h) algorithms (by dividepruneandconquer, 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. Giftwrapping (O(nh)).
[Ref: Ch 3.4.1 of PS]

Sep 19: Randomized incremental (O(n log n)).
[Ref: Ch 11 of BKCO]

Sep 24: Divideandconquer (O(n log n)).
[Refs: my writeup on the kinetic interpretation;
my implementations in C++:
"brute force",
giftwrapping and
divideandconquer;
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 pruneandsearch 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. BentleyOttmann sweep.
[Ref: Ch2 of BCKO,
Chazelle and Edelsbrunner's paper (not easy to read!)]

Oct 31: Balaban's divideandconquer. 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: Polygon triangulation...