Fall 2017, Computational Geometry Projects

DUE: before midnight of Dec 17 (Sunday), by email to instructor (taoju@wust..edu)

Grading:

All projects turned in by the due date will get a perfect (100%) score. What will vary is how much the project as a whole is worth. A solid project on one of the below topics is expected to be worth about 20% of your total grade. Projects with a significant "wow" factor may count for as much as 40% of the total grade. You can choose to not to do a final project, in which case your grade will depend solely on the homeworks (about 50%) and exams (about 50%). No late submissions are allowed; they will be treated as no submission. Projects can be done by 1 or 2 person groups.

Project types:

These project ideas are broken up into different categories:

Category One: Pedagogy (Graphical Applets)

The applets are meant to illustrate concepts learned in class --- it is *not* sufficient to just implement the algorithm, your implementation must also highlight (visually) the important points of what the algorithm is doing. COLLABORATION POLICY: There is a great deal of code that is publicly available on the web. You are welcome to use this (e.g. classes that draw graphs, and triangles and nodes, that support balanced binary trees, etc), BUT you must reference where it came from, and clearly indicate WHAT functionality you have added to the original code. Applets that illustrate extension of algorithms in class to more general scenario (e.g., 3-dimensions) will earn extra points.

An example applet. Some possible topics:
  1. An applet showing the running of the "merge-sort" type of convex hull construction algorithm. (The applet should show every edge that is tested as the algorithm runs, including, for example, which edges are tested when finding the common lower tangent of two sub hulls).
  2. An applet showing Kirkpatrick's triangular decomposition data structure for point location (from lecture 13). (The applet should have a side by side picture. On the right, the "decomposition tree", whose root node represent the whole enclosing triangle, and on the left, the original set of points, and the set of triangles which the query point is being tested against).
  3. Algorithm showing randomized incremental construction of trapezoidal map, with, and the search structure that is built up along with it. Could include statistics of "if you inserted the segments in lots of random orders, what is the distribution of the longest search path in the search structure?".

Category Two: Work on Open Problems

This can take the form of a paper (a) describing the current best algorithms for these problems, the best bounds on the running time of these algorithms, and (b) a description of your approaches to these problems. YOU DO NOT have to improve on the best known bounds for these algorithms, but you do have to carefully document what approaches you tried, why they worked/failed. The expected result of this would be a roughly ten page paper (with diagrams and references), or an equivalent length webpage/blog talking about things you tried and how they came out.

Some possible topics:
  1. Can you find a point set where you can add a point and make the total weight of the min-weight triangulation (MWT) smaller? (answer, yes!). Can you find a point set where you can add 2 points and make the weight decrease each time? Can you find a point set of n-points where you can add n additional points, and with each point reduce the weight of the MWT? Can you find a point set where you can keep adding point and keep reducing the weight of the MWT every time? Alternatively, can you prove no such example exists? [Problem suggested by Joe Mitchell, from SUNY Stony Brook].
  2. Any unsolved problem from the Open Problems Project.

Category Three: Applications

One of the claims I've made is that Computational Geometry is useful for many different fields. Here is your chance to help me prove that statement. For this category, pick a problem relevant to other interests of yours, or other problems of your choosing (e.g. routing of large airplane parts through not so much larger warehouses, or match 3-d shapes from data sets captured by the Kinect). You will need to design an algorithm for your problem, analyze its complexity, provide an implementation, and demonstrate the results on practical inputs.

What to turn in:

Your final document or webpage, should include (in addition to any program/applet you created):
  1. Names of people in your group
  2. A specific description of the problem that you are trying to solve, in two sentences or less. This may be an answer to a question like: What does your applet do? What is your visualization trying to show? What open problem were you trying to address?
  3. If you are doing a pedagogical applet
    1. Background information about the problem and approach. Does not need to be long (one or two paragraphs is ok), but state any assumptions that are necessary for your applet/approach to work (e.g. general position, no more than 10 points, etc.)
    2. describe the pseudo-code of the algorithm that you are creating,
    3. highlight what parts of that pseudocode you are animating.
    4. Discuss any interesting choices that you made in the implementation of the algorithm.
  4. If you are working on an open research problem.
    1. Background information about the problem. What is the current best known algorithm? What are the proven theoretical bounds on the problem?
    2. What approaches have you tried? Can you visualize the results? Show sketches of where proof attempts have failed, or example point sets where your (mostly good) algorithm has a bad case? [I understand that what is appropriate depends heavily on what you tried and what your problem is].
  5. If you have an application domain problem:
    1. Background information, what are your specific inputs and outputs (show a visualization, if possible). What are the needs for the problem domain -- is it important that you find the optimal solution? why or why not?
    2. What are the most related projects that others have built?
    3. Describe your algorithm and show example results. Give a complexity analysis of your algorithm, and also show measured running time for different sizes of inputs