CS 498TC, Spring 2018: Computational Geometry
Instructor
Timothy Chan
(tmc, Siebel 3230,
office hours: Wed 3:304:30 & Fri 3:304:30 or by appointment)
Meeting time/place
Wed & Fri 2:003:15, Seibel 1109
Course Work
 5 assignments
 Midterm (March 1 Thursday 7pm9pm)
 Final exam
 For grad students taking the 4credit version, there is also
a presentation of a research paper
Administrivia
Course policies
Academic integrity
Piazza
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:

[BCKO] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars,
Computational
Geometry: Algorithms and Applications (3rd ed.),
SpringerVerlag, 2008

[O] J. O'Rourke,
Computational Geometry in C (2nd ed.),
Cambridge University Press, 1998

[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
(I'll provide copies of my handwritten notes below...)
Jan 17, 19, 24: Convex hull in 2D
 Algorithms: bruteforce (O(n^3)), Jarvis' march (O(n^2)),
Graham's scan (O(n log n)), mergehull (O(n log n)), ...
 Refs: my notes;
[PS Ch3]