A large portion of your grade will come from a semester project. Projects may be submitted by teams of up to two students, although three students may be allowed to do a common project after justifying it to Kyle first. Students may collaborate outside of their teams, with anyone in or out of class (with proper credit). At the end of the semester, each team will submit a written document of around 10 pages and give a short presentation of around 20 minutes. Project reports are due Wednesday, November 25th. They should be submitted by at least one student per group on eLearning as pdfs.

- Theoretical: Attempt to solve an interesting, non-trivial, and preferably open theoretical problem related to computational topology.
- Experimental: Implement and experimentally evaluate a few algorithms or data structures for one or more closely related problems in computational topology. Projects of this type will preferably compare algorithms or data structures that have known theoretical guarantees versus those used in practice in cases where they differ.
- Scholarly: Write a comprehensive survey on a topic relevant to computational topology. Surveys should be a bit longer than theoretical or experimental reports, and they should include a history of the topic; a description of motivating applications; a summary of known results; sketches of the most important algorithms, data structures, and/or proofs; suggestions for future research; and a thorough bibliography.
- Creative: Do something else cool and relevant to computational topology.

- A survey on probabilistic road maps for motion planning
- A survey on algorithms for computing shortest paths in motion planning
- Theoretical research on quickly approximating the diameter of a point set
- Implementing geometric algorithms for problems such as collision detection as part of a mixed reality mobile application
- Theoretical research on the expected computational complexity of Voronoi diagrams where sites can only "see" points in a halfplane and cells are determined by closest site seeing each point
- Experimental evaluation of using different curve similarity algorithms to perform handwriting recognition
- Implementing geometric algorithms for a face morphing/blending application
- Theoretical research on problems involving separating red and blue sets of points
- Survey on ray and arc shooting data structures
- Survey on computing geometric spanners relevant to wireless ad hoc networks

The main ideas behind the project format and large amounts of the language here are due to Jeff Erickson. This page includes a number of good suggestions on where to find good problems both for this class and in the future.