Description:

This class introduces a practitioner's "tool bag" of techniques for geometric computations. The bulk of our attention will go to a survey of techniques for representing, computing, and man- ipulating geometric entities and relationships among them. We will learn how to build, find, compose, and use such tools in practice. We will also take note of theoretical considerations concerning running time, space usage, degeneracy, etc.

We will consider a large number of techniques, discussing the salient features of each (i.e., what one should know to make use of the concept in practice), and pointers to public domain implementations of the technique, if any. The material we will cover is broadly organized according to five areas: geometric representations; algorithms; queries; applications; and visual interaction techniques.

The subject will be based on lectures and presentations, and will meet twice a week for an hour and a half per meeting. There will be a significant lab (design and programming) component, and a significant final project and presentation to the class. There will be no exams. 8 Design Points.