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
- 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
- For grad students taking the 4-credit version, there is also
a presentation of a research paper.
Administrivia
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.)