Syllabus

Description

This is a reading and project course covering a range of topics related to geometric representation and computation.  We will study fundamental data structures and algorithms from computational geometry and computer graphics, their application to practical problems, and techniques for visual inspection of and interaction with geometric entities.

The aim of the course is to gain familiarity with the understanding, crafting, use, augmentation and visual inspection of geometric objects and data structures.   Specifically the course will have these major focuses:

• Geometric representations and data structures;

• Algorithms to construct such data structures;

• Queries defined on geometric data structures;

• Visual inspection and interaction techniques; and

• Applications of all of the above.

Format

A typical class meeting will consist of an instructor or student presentation of papers and software, and a discussion of the material co-led by the student and instructor. Each lecture, one student will be expected (given several weeks' notice) to summarize the material for that lecture and help lead a discussion of the readings. One week before the student is to present, s/he will be expected to submit a "pre-talk" (a draft version of the overheads to be used) and an initial treatment of the "talking points" suggested by the teacher, as well as (of course) other discussion topics the student wishes to cover in class

Assignments

There will be several small programming assignments.  These are intended to get everyone familiar with the issues of crafting technically substantive and visually interesting manipulations of geometric entities.

Course project

Each student will, with a partner, propose and complete a substantial programming project related to interactive geometric computation. Many topics will be suggested, but students are of course free to propose their own project topic.  Acceptable projects include but are not limited to an implementation (and improvement) of an algorithm from a paper, a synthesis of techniques from several papers, or a work that explains or advances the state of the art. The projects are expected to have some research content and should be designed with that in mind.

Textbook and References

Computational Geometry:  Algorithms and Applications Mark de Berg (Ed.), Marc van Kreveld, Mark Overmars, and Ottfried Schwarzkopf  ISBN: 3540656200	Computational Geometry in C Joseph O'Rourke	Computational Geometry: an Introduction Franco P. Preparata, Michael Ian Shamos

Course Schedule (Spring 2008)

[modified: 2008/06/11 ]