CS311 Computational Geometry
Project

• The project is due Friday 5/9 for seniors, Friday 5/16 for everyone else.
  
  
• A project plan is due Monday 4/14. This should be a document sketching out what you intend to do, and should contain at least the Intro, Related Works and Proposed Work sections that will eventually go into your final report. I will ask each of you to make a presentation of your idea, please prepare to speak for 10 minutes with slides and 5 minutes for questions. Presentation dates are Wednesday 4/16.
  
  
• The project counts as 30% of your course grade.

• I recommend you first think about the following crude distinction among types of projects:
  • Primarily an implementation of a particular geometric computation.
    • Algorithm known, well-studied, original implementation.
    • A novel task.
    • An application, using existing software tools applied to a particular problem.
    • Exploring existing but complex software: download, install, and test some code.
  • Primarily an investigation of the literature in a particular area. The result here would be an exposition on a particular topic, explaining its significance and what is going on in that area. Perhaps 15 pages should be a target length.
  • An investigation of an open problem.
    
    
• Sources
  • Comp.graphics.algorithms FAQ.
  • David Eppstein's Geometry Junkyard.
  • Jeff Erickson's Comp Geom Pages.
  • The Open Problems Project.
  • Use the Web! Search in google under various keywords.

Possible Projects

• Flip graph animation. This is a programming project focusing on graphical output, a web-ready applet might be nice.
  
  
• Voronoi diagrams in nature. Really explain the giraffe coloring, spider webs, and other connections. This would require a good amount of literature investigation and exposition.
  
  
• Voronoi diagrams of unusual things. Implement and compute Voronoi for interesting/unusual sites (i.e. craters of the moon, world airports, applications to architecture, Voronoi fractals, mosaic images, or similarity comparison on anything - music, purchase history, suitable roommate)
  more examples
  
  
• Application of generalized Voronoi Diagrams. As we have discussed in class, there are many ways to generalize VD (generalized distance metric, Weighted VD, high-dimensional VD, etc). Examples: Lp Centroidal VD, Stippling via weighted VD, Fracture via high-dimensional VD, Diffusion Diagrams
  
  
• Triangle Meshing. There are a number of high-quality triangulation programs available. Perhaps the best is Triangle - developed by Jonathan Shewchuck at Berkeley. Download and install it, test it, explore it, find some creative use for it, etc. Anything related to meshing such as mesh optimization, mesh smoothing are all good topics too.
  
  
• Quad Meshing. This is related to triangle meshing, but not nearly as widely studied or well understood. Some bounds are established for max (circlepacking) and min/max (quadtree decomposition) angle. Search the literature to find other related papers. This page lists a number of quadmesh generators, most without much quality guarantee.
  
  
• Tetrahedral Meshing. Extension of triangle meshing to 3D. Typical techniques are via advancing front or Delaunay (for example tetgen). Shewchuck also has a number of papers on tetrahedral meshing, including one that achieved a computer-assisted min dihedral angle bound. This is an active research area with many publications, again please use the web to start with literature survey.
  

• Dynamic/motion. Computational Geometry constructs like convex hull, Voronoi diagram and Delaunay triangulation take on whole new challenges when the point set is no longer static (consider cell phones or moving vehicles). This is an active research topic with many possibilities.
  
  
• Curve Reconstruction. As we have seen in lecture, the problem here is: given a set of points that were drawn from a curve, reconstruct the curve. This is a very active area, with several recent advances. O'Rourke has a brief survey article on this that might be a good starting point. Explore the literature on this topic and write a paper about it.
  
  
• Surface Reconstruction. Reconstruction by crosssections: given 2D slices through a 3D object, reconstruct the surface by stacking the slices and creating a surface. Reconstruction from point cloud is generally known as meshing, but there are other interesting techniques as well. This is a rich, active research area with many current problems.
  
  
• Origami Mathematics. Primarily literature survey and exposition.
  
  
• CGAL. Explore CGAL. It is not easy to use. But it is extraordinarily powerful - serious C++ code! CGAL Home Page