(
Lime-basil Triangulation,
Dinara Kasko, 2016.)
CS 274
Jonathan
Shewchuk |
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, restricted Delaunay triangulations, arrangements of lines and hyperplanes, Minkowski sums, Reeb graphs and contour trees; relationships among them. Geometric duality and polarity. Upper Bound Theorem, Zone Theorem.
Algorithms and analyses: Sweep algorithms, incremental construction, divide-and-conquer algorithms, randomized algorithms, backward analysis. Numerical predicates and constructors, 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), segment trees, 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, curve reconstruction and surface reconstruction, robot motion planning.
Here are Homework 1, Homework 2, Homework 3, Homework 4, Homework 5, and the Project.
The best related sites:
Topic | Readings | Assignment Due | |
1: January 23 | Two-dimensional convex hulls | Chapter 1, Erickson notes | . |
2: January 28 | Line segment intersection | Sections 2, 2.1 | . |
3: January 30 | Overlay of planar subdivisions | Sections 2.2, 2.3, 2.5 | . |
4: February 4 | Polygon triangulation | Sections 3.2–3.4 | . |
5: February 6 | Delaunay triangulations | Sections 9–9.2; my Chapter 2 | . |
6: February 11 | Delaunay triangulations | Sections 9.3, 9.4, 9.6 | . |
7: February 13 | Voronoi diagrams | Sections 7, 7.1, 7.5 | . |
February 18 | Presidents' Day | . | . |
8: February 20 | Planar point location | Chapter 6 | Homework 1 |
9: February 25 | Duality; line arrangements | Sections 8.2, 8.3 | . |
10: February 27 | Zone Theorem; discrepancy | Sections 8.1, 8.4 | . |
11: March 4 | Polytopes | Matoušek Chapter 5 | . |
12: March 6 | Polytopes and triangulations | Seidel Upper Bound Theorem | Homework 2 |
13: March 11 | Small-dimensional linear programming | Seidel T.R.; Sections 4.3, 4.6 | . |
14: March 13 | Small-dimensional linear programming | Section 4.4; Seidel appendix | . |
15: March 18 | Higher-dimensional convex hulls | Seidel T.R.; Secs. 11.2 and 11.3 | . |
16: March 20 | Higher-dimensional Voronoi; point in polygon | Secs. 11.4, 11.5 | Homework 3 |
March 25–29 | Spring Recess | ||
17: April 1 | Geometric robustness | Lecture notes | . |
18: April 3 | Binary space partitions | Sections 12–12.3 | . |
19: April 8 | Binary space partitions | Section 12.5; BSP FAQ | . |
20: April 10 | BSP applications; nearest neighbors | Section 2.4; Arya et al. | Homework 4 |
21: April 15 | Motion planning; Minkowski sums | Sections 13–13.4 | . |
22: April 17 | Visibility graphs | Chapter 15; Khuller notes | . |
23: April 22 | Triangular meshing | Ruppert | . |
24: April 24 | Tetrahedral meshing | Labelle & Shewchuk | Project |
25: April 29 | Curve reconstruction | Dey & Kumar | . |
26: May 1 | Surface reconstruction | Amenta et al. | . |
27: May 6 | Quadratic programming | Matoušek et al. | Homework 5 |
For January 23, here are Jeff Erickson's lecture notes on two-dimensional convex hulls.
For February 6, 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 4 and 6, if you want to supplement my lectures, most of the material comes from Chapter 5 of Jiří 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 6, 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 11 & 13), the Clarkson–Shor convex hull construction algorithm (March 18), 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 13, 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.
For April 1, here are my Lecture Notes on Geometric Robustness.
For April 8 and 10, here is the compilation of BSP Tree Frequently Asked Questions.
For April 10, the best paper I know about how to implement a k-d tree is Sunil Arya and David M. Mount, Algorithms for Fast Vector Quantization, Data Compression Conference, pages 381–390, March 1993. See also 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 17, here are Samir Khuller's notes on visibility graphs.
On April 22, we study the Delaunay refinement algorithm for triangular mesh generation by Jim Ruppert, A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, Journal of Algorithms 18(3):548–585, May 1995.
On April 24, we study the octree-based algorithm for tetrahedral mesh generation by François Labelle and Jonathan Richard Shewchuk, Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles, ACM Transactions on Graphics 26(3), August 2007. (Special issue on Proceedings of SIGGRAPH 2007.)
On April 29, we study the NN-Crust algorithm by Tamal K. Dey and Piyush Kumar, A Simple Provable Algorithm for Curve Reconstruction, Proceedings of the Tenth Annual Symposium on Discrete Algorithms (Baltimore, Maryland), pages 893–894, January 1999. My lecture includes Lemma 1 from this pioneering paper, which Dey and Kumar use in their correctness proof: Nina Amenta, Marshall Bern, and David Eppstein, The Crust and the Beta-Skeleton: Combinatorial Curve Reconstruction, Graphical Models and Image Processing 60/2(2):125–135, 1998.
For May 1, I suggest reading this paper the Cocone algorithm. Feel free to skip the proofs, but read the theorems. Nina Amenta, Sunghee Choi, Tamal K. Dey, and N. Leekha, A Simple Algorithm for Homeomorphic Surface Reconstruction, International Journal of Computational Geometry and Applications 12(1–2):125–141, 2002.
For May 6, I don't know of any reference that describes quadratic programming the way I want to teach it. A fast algorithm can be found in Jiří Matoušek, Micha Sharir, and Emo Welzl, A Subexponential Bound for Linear Programming, Algorithmica 16(4–5):498–516, October 1996, but they don't discuss quadratic programming specifically; rather, they present an “abstract framework” that includes quadratic programming.
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.)