CS380 Computational Geometry
Project
- The project is due on the last day of exam period (Friday 5/17 noon).
- A project plan is due Thursday April 18. 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 20 minutes with slides and 10-15 minutes for questions. Presentation dates are Tuesday 4/23 and Thursday 4/25.
- The project counts as 25% 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
Possible Projects
Any list I make will be too short, and might constrain you. Please consider these
as example possibilities only!
- 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, or similarity comparison on anything - music, purchase history, suitable roommate)
- Triangle Meshing. There are a number of high-quality triangulation programs available.
Perhaps the best is that developed by Jonathan Shewchuck at Berkeley.
Download and install it, test it, explore it, describe it, etc.
- 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, with 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