(Untitled, Till Rickert, Shift 2005 Calendar.)

CS 274
Computational Geometry

Jonathan Shewchuk

Spring 2013
Mondays and Wednesdays, 2:30-4:00 pm
320 Soda Hall

Office hours:
Mondays, 7:10-8 pm, 283 Soda
Fridays, 3:10-4 pm, 529 Soda

Combinatorial geometry: Polygons, polytopes, triangulations, planar and spatial subdivisions. Constructions: triangulations of polygons, convex hulls, intersections of halfspaces, Voronoi diagrams, Delaunay triangulations, arrangements of lines and hyperplanes, Minkowski sums; 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, and Minkowski sums.

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:

Resources for dealing with robustness problems (in increasing order of difficulty):

Textbook

Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational Geometry: Algorithms and Applications, third edition, Springer-Verlag, 2008. ISBN # 978-3-540-77973-5. Or, second revised edition, Springer-Verlag, 2000. ISBN # 3-540-65620-0.
Known throughout the community as the Dutch Book.


Lectures

The following schedule is tentative; changes are likely. Chapter headings refer to the second revised edition. Homeworks will be irregularly assigned, and are due at the start of class. Homeworks are mostly to be done alone, without help from or discussion with other humans; but each homework has one or two group problems, which you may do with one or two other students. (See Homework 1 for detailed rules.)

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 .
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 .
March 25–29 Spring Recess
17: April 1 k-d trees Sections 5–5.2 .
18: April 3 Range trees Sections 5.3–5.6 Homework 3
19: April 8 Interval trees; closest pair in point set Sections 10–10.1; Smid Sec. 2.4.3 .
20: April 10 Segment trees Section 10.3 .
21: April 15 Geometric robustness Lecture notes .
22: April 17 Binary space partitions Sections 12–12.3 Homework 4
23: April 22 Binary space partitions Sections 12.5, 2.4, BSP FAQ .
24: April 24 Robot motion planning Sections 13–13.2 .
25: April 29 Minkowski sums Sections 13.3–13.5 Project
26: May 1 Visibility graphs Chapter 15; Khuller notes .
27: May 6 Nearest neighbor search; order k Voronoi . Homework 5

For January 23, here are Jeff Erickson's lecture notes on two-dimensional convex hulls.

For March 4 and 6, 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 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 (October 19), 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.

On April 8, 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 15, here are my Lecture Notes on Geometric Robustness.

For April 22, here is the BSP FAQ.

For May 1, here are Samir Khuller's notes on visibility graphs.

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.)


Geometry Applets

These applets can be quite helpful in establishing your geometric intuition for several basic geometric structures and concepts.

Prerequisites

Grading



Supported in part by the National Science Foundation under Awards ACI-9875170, CMS-9980063, CCR-0204377, CCF-0430065, CCF-0635381, IIS-0915462, and EIA-9802069, in part by a gift from the Okawa Foundation, and in part by an Alfred P. Sloan Research Fellowship.
(Radiolarian Color Painting. Ernst Haeckel, zoologist, 1834–1919.)