(Untitled, Till Rickert,
Shift 2005
Calendar.)
CS 274
Jonathan Shewchuk and
Marc Khoury Combinatorial geometry: Polygons, polytopes, triangulations and simplicial complexes, planar and spatial subdivisions. Constructions: triangulations of polygons and point sets, convex hulls, intersections of halfspaces, Voronoi diagrams, Delaunay triangulations, arrangements of lines and hyperplanes, Minkowski sums, Reeb graphs and contour trees; relationships among them. Geometric duality and polarity. Numerical predicates and constructors. Upper Bound Theorem, Zone Theorem. Algorithms and analyses: Sweep algorithms, incremental construction, divide-and-conquer algorithms, randomized algorithms, backward analysis, geometric robustness. Construction of triangulations, convex hulls, halfspace intersections, Voronoi diagrams, Delaunay triangulations, arrangements, Minkowski sums, and Reeb graphs. Geometric data structures: Doubly-connected edge lists, quad-edges, face lattices, trapezoidal maps, conflict graphs, history DAGs, spatial search trees (a.k.a. range search), binary space partitions, quadtrees and octrees, visibility graphs. Applications: Line segment intersection and overlay of subdivisions for cartography and solid modeling. Triangulation for graphics, interpolation, and terrain modeling. Nearest neighbor search, small-dimensional linear programming, database queries, point location queries, windowing queries, discrepancy and sampling in ray tracing, robot motion planning. |
Here are Homework 1, Homework 2, Homework 3, Homework 4, and Homework 5.
The best related sites:
Topic | Readings | Assignment Due | |
1: January 21 | Two-dimensional convex hulls | Chapter 1, Erickson notes | . |
2: January 26 | Line segment intersection | Sections 2, 2.1 | . |
3: January 28 | Overlay of planar subdivisions | Sections 2.2, 2.3, 2.5 | . |
4: February 2 | Polygon triangulation | Sections 3.2–3.4 | . |
5: February 4 | Delaunay triangulations | Sections 9–9.2; my Chapter 2 | . |
6: February 9 | Delaunay triangulations | Sections 9.3, 9.4, 9.6 | . |
7: February 11 | Voronoi diagrams | Sections 7, 7.1, 7.5 | . |
February 16 | Presidents' Day | . | . |
8: February 18 | Planar point location | Chapter 6 | Homework 1 |
9: February 23 | Duality; line arrangements | Sections 8.2, 8.3 | . |
10: February 25 | Zone Theorem; discrepancy | Sections 8.1, 8.4 | . |
11: March 2 | Polytopes | Matoušek Chapter 5 | . |
12: March 4 | Polytopes and triangulations | Seidel Upper Bound Theorem | Homework 2 |
13: March 9 | Small-dimensional linear programming | Seidel T.R.; Sections 4.3, 4.6 | . |
14: March 11 | Small-dimensional linear programming | Section 4.4; Seidel appendix | . |
15: March 16 | Higher-dimensional convex hulls | Seidel T.R.; Secs. 11.2 and 11.3 | . |
16: March 18 | Higher-dimensional Voronoi; point in polygon | Secs. 11.4, 11.5 | . |
March 23–27 | Spring Recess | ||
17: March 30 | k-d trees | Sections 5–5.2 | . |
18: April 1 | Range trees | Sections 5.3–5.6 | Homework 3 |
19: April 6 | Interval trees; closest pair in point set | Sections 10–10.1; Smid Sec. 2.4.3 | . |
20: April 8 | Segment trees | Section 10.3 | . |
21: April 13 | Geometric robustness | Lecture notes | . |
22: April 15 | Binary space partitions | Sections 12–12.3 | Homework 4 |
23: April 20 | Binary space partitions | Section 12.5 | . |
24: April 22 | BSP applications; nearest neighbors | Section 2.4; BSP FAQ; Arya et al. | . |
25: April 27 | Motion planning; Minkowski sums | Sections 13–13.4 | Project |
26: April 29 | Visibility graphs | Chapter 15; Khuller notes | . |
27: May 4 | Reeb graphs (and contour trees) | Harvey et al. | Homework 5 |
For January 21, here are Jeff Erickson's lecture notes on two-dimensional convex hulls.
For February 4, you might (optionally) also be interested in Chapter 2 from my book: Siu-Wing Cheng, Tamal Krishna Dey, and Jonathan Richard Shewchuk, Delaunay Mesh Generation, CRC Press (Boca Raton, Florida), December 2012.
For March 2 and 4, if you want to supplement my lectures, most of the material comes from Chapter 5 of Jirí Matoušek, Lectures on Discrete Geometry, Springer (New York), 2002, ISBN # 0387953744. He has several chapters online; unfortunately Chapter 5 isn't one of them.
For March 4, I will hand out Raimund Seidel, 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.
Seidel's linear programming algorithm (March 9 & 11), the Clarkson–Shor convex hull construction algorithm (March 16), and Chew's linear-time algorithm for Delaunay triangulation of convex polygons are surveyed 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 11, I will hand out the appendix from Raimund Seidel, 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, I think this appendix is a better guide than the Dutch Book.
On April 6, I will teach a randomized closest pair algorithm from Section 2.4.3 of Michiel Smid, Closest-Point Problems in Computational Geometry, Chapter 20, Handbook on Computational Geometry, J. R. Sack and J. Urrutia (editors), Elsevier, pp. 877–935, 2000. Note that this is a long paper, and you only need pages 12–13.
For April 13, here are my Lecture Notes on Geometric Robustness.
For April 22, here is the BSP FAQ, and here is Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu, An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions, Journal of the ACM 45(6):891–923, November 1998.
For April 29, here are Samir Khuller's notes on visibility graphs.
For May 4, I will hand out William Harvey, Yusu Wang, and Rephael Wenger, A Randomized O(m log m) Time Algorithm for Computing Reeb Graphs of Arbitrary Simplicial Complexes, Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry, pages 267–276.
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. 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.)