CS 860: Algorithms for Polyhedra, Fall 2004

www.cs.uwaterloo.ca/~alubiw/polyhedra.html

Anna Lubiw, Department of Computer Science, University of Waterloo
alubiw@uwaterloo.ca, (519) 888-4567, ext. 4449


Contents: Organization, Course Outline, Resources, Lectures, Assign. 1, Assign. 2, Presentations.


Organization

Time and Place: Monday and Wednesay, 11:30--1:00, DC 3313, starting Monday September 13.
Classes will consist of lectures, student presentions of papers, and problem sessions.

Credit:


Course Outline

This will be a research level course in computational geometry, concentrating on algorithms that deal with polyhedra in three dimensions.

Polyhedra have fascinated mathematicians for centuries, and this course will at least touch on some of this large body of work, revisiting classical results from a more algorithmic point of view. These days, polyhedra and polygonal meshes are ubiquitous in computer graphics, computer aided design, medical imaging, and scientific computing; applicability to these areas will guide the selection of topics for this course, although it is not an applications course.

The course will emphasize design, correctness and analysis of algorithms.

Topics: (Preliminary list)

Background: I will not assume that students have a previous course in computational geometry, and will try to keep the overlap with our basic graduate course in computational geometry, CS 763, as small as possible, to avoid boring those who have taken, or will take that course. I will assume a background in algorithms and data structures equivalent to a decent undergraduate course.

Books

Web Pages

Polyhedra

Computational Geometry Algorithms and Software

Finding Papers


Lectures

For each class, I've listed the topics covered, pages handed out, and references.

Lecture 1, Sept. 13: Introduction to Polyhedra

Handouts: References: Thought Exercise: which polyhedra make fair dice? See George Hart's dice page, MathWorld's isohedron page.

Open Problem: Can all convex polyhedra be edge unfolded? See the Open Problems Project.


Lecture 2, Sept. 15: Classic concepts and results on polyhedra

References:

Lecture 3, Sept. 20: Obtaining Polyhedra: I. from point sets

References:

Lecture 4, Sept. 22

References: Exercise: Find n points in 3-D with Omega(n^2) Delaunay tetrahedra.

Lecture 5, September 27

References: Possible Papers to Present:
(Present an over-view of the paper in 20 minutes.) Possible Project:

Lecture 6, September 29

References:

Lecture 7, October 4

References: Possible Papers to Present:
(Present an over-view of the paper in 20 minutes.)

Lecture 8, October 6

References: Possible Papers to Present:
(Present an over-view of the paper in 20 minutes.)

Lecture 9, October 18

References: Possible Papers to Present:
(Present an over-view of the paper in 20 minutes.)

Lecture 10, October 20

References: Possible Papers to Present:
(Present an over-view of the paper in 20 minutes.)

Lecture 11, October 25

References:

Lecture 12, October 27

References:

Lecture 13, November 1

References:

Lecture 14, November 3

References:

Lecture 15, November 8: Shortest Paths

References:

Lecture 16, November 8


Lecture 17, November 15

References:

Lecture 18, November 17

References:

Lecture 19, November 22

References:

Lecture 20, November 24

References:

Lecture 21, November 29


Lecture 22, December 1