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,
Feb 21); [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, 28, Mar 2: Linear programming in low dimensions
 Algorithms: Megiddo/Dyer's pruneandsearch in 2D and 3D (O(n) time),
Seidel's randomized incremental (O(n) expected),
Clarkson's random sampling (O(n) expected, both recursive and iterativereweighting versions)
 Refs: my notes (Feb 23,
Feb 28,
Mar 2);
[BCKO, Ch4] (covers Seidel's), [PS, Ch7.2.5] (covers
Megiddo's in 2D), [Motwani and Raghavan, Randomized algorithms, 1995, Ch9]
(covers Seidel's and Clarkson's),
Megiddo's paper,
Clarkson's paper,
Matousek, Sharir, and Welzl (refinement of Seidel's)
Mar 7, 9, 14: Line segment intersection and arrangements
 Algorithms: incremental (for arrangements of lines O(n^2)),
Bentley and Ottmann's sweep (O((n+k)log n) time),
Balaban's algorithm (O(n log^2 n + k) version)
 Combinatorics: the zone theorem
 Refs: my notes (May 7,
May 9,
May 14);
[BCKO] (Ch8 on arrangement of lines and
Ch2 on BentleyOttmann),
Chazelle and Edelsbrunner's paper and
Balaban's paper (not
easy to read)
Mar 16, 28: Point location
 Algorithms: bruteforce (O(n^2) space, O(log n) query),
divideandconquer => segment trees (O(n log n) space, O(log^2 n) query),
sweep => persistent search trees (O(n log n) space, O(log n) query),
randomized incremental (O(n) space, O(log n) query),
Kirkpatrick's pruneandsearch (O(n) space/preprocessing, O(log n) query)
 Refs: my notes (May 16,
May 28);
[BCKO, Ch6]
covers the randomized incremental method; [O] and
[PS, Ch2.2] cover Kirkpatrick's method
Mar 30: Polygon triangulation
Apr 4, 6: Applications of polygon triangulation
 The "art gallery" problem, a motion planning problem
 Combinatorics: union complexity of Minkowski sums
 Refs: my notes; [BKCO, Ch3 and
Ch13]; see also [O] on art gallery and motion planning; a survey on
union complexity
Apr 11, 13, 18: Range searching
 Orthogonal case: range tree (O(n log n) space, O(log^2n) query)
 Triangle/halfplane case: Willard's
partition tree (O(n) space, O(n^0.793) query via "hamsandwich cuts")
 Refs: my notes (Apr 11,
Apr 13,
Apr 18);
[BKCO, Ch5
and Ch16]; Agarwal and Erickson's
survey
Apr 20: BSP trees
 Algorithms: orthogonal 2D case (O(n) size), general 2D case (O(n log n) size by
randomized incremental construction or by segment tree)
 Refs: my notes;
[BKCO, Ch 12]; Paterson and Yao's original paper
(and Toth's improvement)