Overview

For the final project in this class, your task is to choose an area of research in geometric algorithms and design a project around it. Some possible options include: (1) writing a research term paper summarizing and/or evaluating current results in the field, (2) implementing, experimenting, and/or evaluating an algorithm from a recent (or not so recent) paper, (3) attempting an original result that improves upon an unsolved problem in this area.

The project consists of four parts:

  1. A project proposal (initial proposal due Feb 22 01:59:59 PM)
  2. Implementation and/or research
  3. A written final project report (due Apr 29 11:59:59 PM)
  4. A final project presentation

Example project formats might include:

  • Investigating a topic area in the class in greater detail by reading and reporting on relevant research papers. In doing so, the expectation would be to educate the class beyond what we have covered in the standard lectures. Treat this like a potential survey that could cover papers we were not able to otherwise discuss in detail.
  • Investigating an unsolved or only partially solved result in geometric algorithms. This could be exploring some of the topics described in repositories such as The Open Problems Project, Jeff Erickson’s Open Problems, or open problems from the Geometry Junkyard. The expectations here would be to aim for a new research paper in this area that could be submitted.
  • Implementing and/or experimenting with existing (or new!) algorithms. Such implementations could focus on educational purposes (e.g. visualizing the behavior of existing computational geometry algorithms) or for understanding robustness and/or practical considerations (e.g. tolerance to input sets that violate standard assumptions, differences between asymptotic behavior its constants). The expectation here would be a deliverable implementation, and potentially a submitted paper or product. You may find the information on the SoCG Multimedia Track a helpful guide here, although the deadline to submit might be too restrictive.

Of course, you are welcome to deviate from the above if you have a creative idea. Simply let me know!

Project Proposal

Due at the end of week 7, you must submit a one page (or less) project proposal outlining what your final project will be via email. The email should use the subject line CSC 537 Final Project Proposal. All other emails with project proposals will be ignored. Following that will be a one week “revision” cycle, where you and I will negotiate the expectations for your final project. We will schedule meetings to discuss on an ad hoc basis depending on whether or not we can converge over email.

Your proposal should, at a minimum, include:

  • A concise description of what you will propose to do, including any references to recent research you will use
  • A list of deliverables, describing the final products and/or software artifacts you will produce.
  • Any intermediate milestones or due dates that would like me to enforce or seek out feedback.

I do recommend you strive to pick a project you are most interested in. If you are uncertain, contact me prior to the deadline for proposals and I can offer more suggestions.

Implementation and Research

Once approved, I expect you to be using the time between now and the start of presentations to be implementing and otherwise working on this research project. While no intermediate milestones are required, I am happy to provide informal feedback periodically throughout the duration.

Final Project Report and Presentation

You should prepare a final report describing your experiences in this project. I expect this to be typeset, ideally using LaTeX. You should treat this report as you would a draft of a research paper, in particular you should introduce the problem, survey any related work, describe any relevant methods, report any results, and discuss your findings. While there is no page limit, ideally this should be at least a few pages describing, in detail, the work you prepared for the final project.

During the last three weeks of class, you will be required to give a presentation of at least 25 minutes reporting on your results. Such presentations should be treated as a mini lecture, where you summarize the efforts of your research and explain the key results. Such lectures can also include sample collaborative exercises for the class.

Submission and Grading

All materials should be submitted to me via email by Apr 29 11:59:59 PM. Feel free to send a link to a private git repository, shared directory on google drive or dropbox, or just use a zip file. Please inform me if you have special needs for submission. The email should use the subject line CSC 537 Final Project Submission. All other emails with project submissions will be ignored.

The project report and its results are worth half the total grade. Reports will be graded by their completeness and organization. If you have implemented anything, I expect you also to submit the implementation in a form where I can run it with minimal effort.

The project presentation is worth the other half of the total grade, and it will be evaluated on completeness and presentation effectivenes. Please submit any presentation materials such as slides.

This assignment will count for 10% of your final grade. Extra credit may be assigned for going beyond the specifications of the assignment.