Piazza
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:
-
[BCKO] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars,
Computational
Geometry: Algorithms and Applications (3rd ed.),
Springer-Verlag, 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,
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
(I'll provide copies of my handwritten notes below...)
Jan 17, 19, 24, 26: Convex hull in 2D
- Algorithms: brute-force (O(n^3)), Jarvis' march (O(n^2)),
Graham's scan (O(n log n)), merge-hull (O(n log n), versions without and
with pre-sorting), two output-sensitive algorithms
by divide-prune-and-conquer and by grouping (O(n log h))
- Lower bounds: reduction from sorting, Ben-Or's result
on algebraic decision trees (Omega(n log n))
- Refs: my notes (Jan 17,
Jan 19, Jan 24,
Jan 26);
[PS Ch3];
Ben-Or'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: gift-wrapping (O(nh)), incremental (sketch only:
O(n^2) worst-case or O(n log n) randomized), divide-and-conquer (O(n log n) deterministic)...
- Refs: my notes (Feb 2,
Feb 7,
Feb 9); [O, Ch4];
[PS, Ch3.4] (which covers
gift-wrapping and divide-and-conquer);
[BKCO, Ch11] (which covers a randomized incremental algorithm)
-
My implementations (in C++):
"brute force",
gift-wrapping and
divide-and-conquer
(see my write-up on the kinetic interpretation
of the divide-and-conquer algorithm)
Feb 14, 16, 21: Voronoi diagrams and Delaunay triangulations
- Motivation (post office problem), properties, and
connection with lower envelopes and convex hulls in 3-d
(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 prune-and-search in 2D and 3D (O(n) time),
Seidel's randomized incremental (O(n) expected),
Clarkson's random sampling (O(n) expected, both recursive and iterative-reweighting 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 Bentley-Ottmann),
Chazelle and Edelsbrunner's paper and
Balaban's paper (not
easy to read)
Mar 16, 28: Point location
- Algorithms: brute-force (O(n^2) space, O(log n) query),
divide-and-conquer => 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 prune-and-search (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 "ham-sandwich 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)
Apr 25, 27: Klee's measure problem
- Algorithms: sweep (O(n log n) in 2D by Bentley, O(n^{3/2} log n) in 3D
by Overmars and Yap),
divide-and-conquer (O(n log n) in 2D, O(n^{3/2}) in 3D by me)
- Conditional lower bounds: reduction from 3-cycle
- Refs:
my notes (Apr 25,
Apr 27);
[PS, Sec 8.4]; my paper (2013)
May 2: Lower envelopes of line segments
- combinatorial complexity O(n alpha(n))
- Refs:
my notes;
Agarwal and Sharir's survey