Clarkson University

CS 446 / CS 556: Computational Geometry

Course Syllabus -- Fall 2004

Professor: William Hesse
Office: Science Center 383
Phone: 268-2387

Office hours:
Monday 9:00-11:00
Tuesday 12:00-2:00
Wednesday 2:00-3:00
Friday 10:00-12:00
Or by appointment

Course Objectives:

  1. Students will learn common data structures for representing and searching 2-dimensional and 3-dimensional geometric objects.
  2. Students will learn important algorithms and new algorithmic techniques for solving geometric computational problems.
  3. Graduate students will read papers from the computational geometry research literature and gain an appreciation for the current state of research in this area.
  4. Students will implement a major project that solves an interesting problem in computational geometry, which will require them to apply the course material in innovative ways.
  5. Implementations will visually portray the actions and results of geometric algorithms, using graphics and animation techniques.

Textbook: "Computational Geometry in C, 2nd Ed.",
by Joseph O'Rourke. Published by Cambridge University Press.


1 Polygon Triangulation
2 Polygon Partitioning
3 2D Convex Hulls
Not in
Curves and Curved Surfaces
4 3D Convex Hulls
5 Voronoi Diagrams
7 Search and Intersection
8 Motion Planning


Assignments: The assignments will be programming projects, to be completed individually. Reasonable amounts of help from fellow students and the instructor are acceptable, and should be credited in the documentation.

Late Policy Late work will be penalized 20% per week. The final project must be submitted by the last day of classes. No work submitted after the end of the final exam period will be considered in computing the final grade in the course. Academic integrity: Assignments may be discussed with other students. However, do not look at other students' solutions until you have solved the problem yourself. You can give help to other students, but you may not just tell them the answer. Feel free to discuss the assignments and strategies for solving them (algorithms), but write the code yourself.

Author: William Hesse
Last Modified: Sep 10, 2004