CS 274 Computational Geometry
Jonathan Shewchuk Synopsis: Constructive problems in computational geometry: convex hulls, triangulations, Voronoi diagrams, Delaunay triangulations, arrangements of lines and hyperplanes, subdivisions. Relationships among these problems. Techniques in computational geometry: data structures, incremental construction, divide-and-conquer algorithms, randomized algorithms, backward analysis, geometric robustness. Line segment intersection, planar subdivisions, spatial search trees, visibility graphs, small-dimensional linear programming. Applications: Nearest neighbor search; triangulation for graphics, interpolation, and terrain modeling; database queries, point locations queries, and windowing queries; collision detection; discrepancy and sampling in ray tracing; robot motion planning; cartography; art gallery theorems. |
The best related sites:
Topic | Readings | Due Thursday | |
1: January 21 | Two-dimensional convex hulls | Chapter 1 | . |
2: January 23 | Line segment intersection | Sections 2, 2.1 | . |
3: January 28 | Overlay of planar subdivisions | Sections 2.2, 2.3, 2.5 | . |
4: January 30 | Polygon triangulation | Sections 3.2-3.4 | . |
5: February 4 | Delaunay triangulations | Sections 9-9.2 | . |
6: February 6 | Delaunay triangulations | Sections 9.3, 9.4, 9.6 | Homework 1 |
7: February 11 | Marshall Bern on interpolation | . | . |
8: February 13 | Vladlen Koltun on Davenport-Schinzel sequences | . | . |
9: February 18 | Delaunay triangulations, Voronoi diagrams | Sections 7, 7.1, 7.3 | . |
10: February 20 | Planar point location | Chapter 6 | Homework 2 |
11: February 25 | Small-dimensional linear programming | Sections 4.3, 4.6; Seidel T.R. | . |
12: February 27 | Leonidas Guibas on kinetic data structures | . | . |
13: March 4 | Small-dimensional linear programming | Section 4.4; Seidel appendix | . |
14: March 6 | Duality; line arrangements | Sections 8.2, 8.3 | . |
15: March 11 | Zone theorem; discrepancy | Sections 8.1, 8.4 | . |
16: March 13 | Polytopes and triangulations | . | Homework 3 |
17: March 18 | Carlo Séquin on splines | . | . |
18: March 20 | Carlo Séquin on splines | . | . |
March 24-28 | Spring Recess | . | . |
19: April 1 | Polytopes and triangulations | Seidel article; Secs. 11.4 and 11.5 | . |
20: April 3 | Higher-dimensional convex hulls | Seidel T.R.; Secs. 11.2 and 11.3 | . |
21: April 8 | k-d trees | Sections 5-5.2 | . |
22: April 10 | Range trees | Sections 5.3-5.6 | . |
23: April 15 | Interval trees | Sections 10-10.1 | . |
24: April 17 | Segment trees | Section 10.3 | . |
25: April 22 | Binary space partitions | Sections 12-12.3 | . |
26: April 24 | Binary space partitions | Sections 12.4, 2.4, BSP FAQ | Homework 4 |
27: April 29 | Vladlen Koltun on Minkowski sums | Sections 13-13.2 | . |
28: May 1 | Robot motion planning | Sections 13.3-13.5 | . |
May 2 | . | . | Project, 5 pm |
29: May 6 | Visibility graphs | Chapter 15; Khuller notes | . |
30: May 8 | Geometric robustness | Lecture notes | . |
31: May 13 | Loose ends | . | . |
May 22 | . | . | Homework 5, 5 pm |
For January 21, here are Jeff Erickson's lecture notes on two-dimensional convex hulls.
Chew's linear-time algorithm for Delaunay triangulation of convex polygons (February 18), Seidel's linear programming algorithm (February 25 & March 4), and the Clarkson-Shor convex hull construction algorithm (April 3) are reported in Raimund Seidel, Backwards Analysis of Randomized Geometric Algorithms, Technical Report TR-92-014, International Computer Science Institute, University of California at Berkeley, February 1992. Warning: online paper is missing the figures. I'll hand out a version with figures in class.
For March 4, I will hand out the appendix from Raimund Seidel's Small-Dimensional Linear Programming and Convex Hulls Made Easy, Discrete & Computational Geometry 6(5):423-434, 1991. For anyone who wants to implement the linear programming algorithm, this appendix is a better guide than the Dutch Book. Unfortunately, there is no online version.
For April 1, I will hand out Raimund Seidel's The Upper Bound Theorem for Polytopes: An Easy Proof of Its Asymptotic Version, Computational Geometry: Theory and Applications 5:115-116, 1985. Don't skip the abstract: the main theorem and its proof are both given in their entirety in the abstract, and are not reprised in the body at all. Unfortunately, there is no online version.
For April 24, here is the BSP FAQ.
For May 6, here are Samir Khuller's notes on visibility graphs.
For May 8, here are my Lecture Notes on Geometric Robustness.
For the Project, read Leonidas J. Guibas and Jorge Stolfi, Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams, ACM Transactions on Graphics 4(2):74-123, April 1985. Unfortunately, there is no online version, but I'll hand it out in class. Feel free to skip Section 3, but read the rest of the paper. See also this list of errors in the Guibas and Stolfi paper, and Paul Heckbert, Very Brief Note on Point Location in Triangulations, December 1994. (The problem Paul points out can't happen in a Delaunay triangulation, but it's a warning in case you're ever tempted to use the Guibas and Stolfi walking-search subroutine in a non-Delaunay triangulation.)