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, 26: 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), versions without and
with presorting), two outputsensitive algorithms
by dividepruneandconquer and by grouping (O(n log h))
 Lower bounds: reduction from sorting, BenOr's result
on algebraic decision trees (Omega(n log n))
 Refs: my notes (Jan 17,
Jan 19, Jan 24,
Jan 26);
[PS Ch3];
BenOr's paper,
C., Snoeyink, and Yap (Sec 3) and
my
other paper (Sec 2)
Jan 31: Applications of convex hulls
Feb 2, 7, 9: Convex hulls in 3D
 Convex polyhedra, duality, combinatorics, representation
 Algorithms: giftwrapping (O(nh)), incremental (sketch only:
O(n^2) worstcase or O(n log n) randomized), divideandconquer (O(n log n) deterministic)...
 Refs: my notes (Feb 2,
Feb 7,
Feb 9); [O, Ch4];
[PS, Ch3.4] (which covers
giftwrapping and divideandconquer);
[BKCO, Ch11] (which covers a randomized incremental algorithm)

My implementations (in C++):
"brute force",
giftwrapping and
divideandconquer
(see my writeup on the kinetic interpretation
of the divideandconquer algorithm)
Feb 14, 16, 21: Voronoi diagrams and Delaunay triangulations
 Motivation (post office problem), properties, and
connection with lower envelopes and convex hulls in 3d
(the lifting map)
 Algorithms: sketch of Fortune's sweep
 Applications: closest pair,
largest empty circle, EMST, "best" triangulation
 Refs: my notes (Feb 14,
Feb 16); [PS] (Ch5,6); [BCKO]
(Ch7 describes Fortune's sweep algorithm
and
Ch9 describes a randomized incremental algorithm); Aurenhammer's survey;
a demo of Fortune's algorithm from
Desmos
Feb 23: Linear programming in low dimensions