Jan/Feb Lecture objectives                    

Objectives for what students will gain from each lecture:

Jan 13

Lecture 1: a brief introduction to the course, lecturer, TA, and text.

Reading: handout ho1, Hamming ch. 1 & N+1, once it is available from the publisher.

Jan 18

Lecture 2: After this lecture, a student should be able to use IEEE 754 floating point arithmetic to explain the different results for the ``3·¹/₃ = 1'' puzzle and the concepts of relative and absolute error.

Reading: handout ho3. (Hamming 2& 3)

Other reading: Kahan has a detailed example of calculations for needle-like triangles http://www.cs.unc.edu/~snoeyink/c/c205/Triangle.pdf.

Jan 20

Lecture 3: The student will be able to solve the rail puzzle using some of the basic elements of numerical analysis that we will assume: Taylor series, Zero finding by bisection and Newton's methods. We also review Horner's rule and Polynomial interpolation. See the MATLAB diary from the lecture.

Reading: (Hamming 3.7, 4, 6, & 14 or any other Numerical Analysis text)

Jan 25

SNOW DAY

Jan 27

SNOW DAY

Due: Problem set #1

Feb 1

The student will be able to derive Melkman's algorithm from its data structure and invariant, and apply it to compute a CSG representation of a polygon.

Reading: Geometric algorithms 1.1, 1.2.2, 1.5.5.

Other Reading: ``An efficient algorithm for finding the CSG representation of a simple polygon'' by David Dobkin, Leonidas Guibas, John Hershberger, and Jack Snoeyink. In SIGGRAPH '88 proceedings: Computer Graphics, 22(4):31-40, 1988. Also Algorithmica, 10:1-23, 1993.

Feb 3

The student will review vectors spaces and their relation to geometry, The student will be able to distinguish between problems that require projective, oriented projective, affine, or Euclidean geometry, and implement these in homogeneous coordinates. (One advantage of this is duality.)

Reading: Geometric algorithms ch 3

Other readings: Jorge Stolfi, ``Oriented Projective Geometry: A framework for geometric computations,'' Academic Press, 1991.

Feb 8

The student will be able to choose a favorite data structure for storing triangulations, to define the Delaunay triangulation, and to prove Euler's relation.

Due: Problem set #2

Reading: Geometric algorithms 4.1-.2, ch 5

Other readings: Leonidas J. Guibas and J. Stolfi, ``Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.'' ACM Trans. Graph., 4(2):74-123, April 1985. Also Dan Litchinski, Graphics Gems IV.

Feb 10

The student will be able to define and use the Delaunay triangulation and Voronoi diagram to do, for example, curve reconstruction and surface interpolation.

Reading: Geometric algorithms ch 5

Feb 15

The student will be able to use perturbation methods to avoid degeneracies in computing convex hulls and Voronoi diagrams, and can explain the relationship to exact geometric computing.

Reading: Geometric algorithms ch 14

Feb 17

Gaussian Elimination and its error analysis

Reading: Hamming 7, 44

Feb 22

Linear least squares and singular value decomposition Two important linear systems topics: 1. Sparseness 2. Eigenvalues and eigenvectors

Reading: Hamming 25, 27, 45

Due: Problem set #3

Feb 24

Applications of singular value decomposition

Take-home midterm handed out, due March 9

Due: Problem set #4

Feb 29

The student will see some other useful geometric representations: complex numbers, quaternions, and Plücker coordinates

Reading: Geometric algorithms ch 3 updated.

Due: Problem set #5

Mar 2

The student will be able to implement simple randomized algorithms to solve linear programming and generalized linear programming (such as the enclosing circle).

May 11

Final exam: place TBA, 8:00am