MCS 481: Final projects

David Dumas

About the final project

For the final project in MCS 481, you will research a topic in computational geometry and produce both a written report and a 20-minute in-class presentation.

The written report is due at 2:00pm on the last day of class, Friday, April 29.

Presentations

Final project presentations will take the place of lectures in the last week of the semester and during the 2-hour final exam period scheduled by the registrar:

Date	Time	Presentations
Mon, Apr 25	2-3pm	Joseph Berner	Time Complexity of the Minimal Art Gallery Algorithm
		Sara Bishop	Covering and Packing Problems in Computational Geometry
Wed, Apr 27	2-3pm	David Chen	Triangulating a Simple Polygon
		Tung Hoang	Graph Planarity
Fri, Apr 29	2-3pm	Min Shen	Linear Programming in higher dimensions
		Justin Martin	Fractional Cascading and its Applications
Wed, May 4	1-3pm	Samuel Cole	Special Cases of TSP
		Paul Dworzanski	3D Mesh Generation in CGAL
		Xiangcheng Yu	Matlab Regular Triangulation for 2 and 3 dimensions
		Eric Lacosse	Perceptrons
		Muhammad Adeel	Topological types of real algebraic curves

Selecting a topic

If you do not have a topic in mind already, read the list of suggestions below. Once you have identified a topic of interest, do some preliminary reading (in the textbook, other computational geometry references, journal articles, etc.) and develop a more detailed proposal for a project on that topic.

Email a project proposal to ddumas@math.uic.edu. Use the subject line

    MCS 481 final project proposal

and include:

• A title for your project
• A few sentences describing what you will do, in somewhat more detail than the topic suggestions below
• A description of what you will turn in at the end of the semester

After I review your proposal, I will contact you and either approve the project or suggest revisions.

General guidelines

Your research should involve more than simply reading in our textbook. Show that you can make use of other resources.

Wikipedia has its uses, but it is not an authoritative reference. Your sources should be written by experts and subject to peer review.

Proposals for coding projects will be considered. The final product must still include a written report describing the algorithm(s) you implemented, the design choices you had to make, etc.

Project suggestions

I have received all of your project proposals. If you still want to see the old list of topic suggestions, here it is.

Other resources

Lists of "open" (i.e. unsolved) problems in discrete and computational geometry:

• The Open Problems Project by Demaine, Mitchell, and O'Rourke
• Open Problems by Jeff Erickson
• Geometry Junkyard: Open problems edited by David Eppstein

Up: MCS 481