CS 763 project
CS 763 Project, University of Waterloo
Fall 2016, Anna Lubiw
Presentation (15 minutes + 5 minutes for discussion/questions) to be done in class.
Written Report due December 5 (later if I'm allowed to).
For your class presentation you must read and report on one paper in computational geometry. A list of suggestions is below. You may pick a paper not on the list -- choose a paper from a reputable computational geometry (or algorithms or graphics) journal or conference, and check your choice with me. You should not report on a survey paper, though you might use a survey paper to help you find a good paper on a particular topic. An alternative to the single-paper report is to tackle an open problem, in which case you should survy what is known and suggest ideas of how to tackle the problem.
Your presentation will be judged based on how well you comprehend and communicate the results in the paper. Keep in mind that your audience is the other students in the class.
Your written report should summarize the paper you presented in class PLUS discuss what comes next on the topic, either work that WAS done in the case of an older paper, or work that MIGHT be done next in the case of a newer paper. Aim for approximately 5 pages. Do not simply repeat the contents of the paper.
For ideas and collections of papers try the following links:
* Google Scholar scholar.google.ca
* The Open Problems Project -- you could pick an open problem and report on the background/partial results
* the Handbook of Computational Geometry has survey articles on many topics (I have a copy you may borrow)
V computational geometry journals:
* Discrete and Computational Geometry
* Computational Geometry: Theory and Applications
* Journal of Computational Geometry
* International Journal of Computational Geometry
* Symposium on Computational Geometry
Some possible topics (click on triangle for list of papers):
this is not a comprehensive list, just some starting points!
> visibility
> simple polygons
> triangulating polygons and planar graphs
> decomposing polygons/polyhedra
> convex hull and problems on convex polyhedra
> Voronoi diagrams, Delaunay triangulations
> curves in the plane
> min spanning tree
> triangulating point sets
> meshing
> surface reconstruction and related
> range searching
> planar point location
> spanners
> motion planning and folding
> robustness, perturbations
> shortest paths