The first half will cover geometric structures, such as convex hulls, Voronoi diagrams, arrangements, triangulations, and spatial data structures. We will explore design and analysis tools such as duality and reductions.
The second half will be devoted to exploring applications of computational geometry to problems in computer graphics. Students will review current research papers and present them to the class, and will submit a course project.
Reading research papers: select one of the topics listed below, and read five or six research papers on the topic. Suggested papers are given. Then, prepare a summary of the papers read, about a half page per paper, describing the material in an accessible manner for others in the class.
Presentations: Give a 30-minute talk on the area chosen. The talk should be high-level enough for everyone to follow the material. Don't get bogged down in the details.
Project: Implement or extend a technique described in the the literature you covered. At some point in the term, we will have a group presentation with all project proposals, 3 to 5 minutes each. It will be fun!
Here are the class evaluations of project proposals.