CS 763: Computational Geometry, Fall 2016

Contents: Organization, Course Outline, Assignments, Resources, Lectures, Project, Presentation Schedule

Announcements

• The written project will be due Monday Dec. 12.
• There will be no lecture on Tuesday Nov. 8. The lecture on Thursday Nov. 10 will be given by Professor Timothy Chan on the topic of range searching.
• Oct. 15. Project info is available above.
• Announcements will be posted on Piazza
• Classes start on Tuesday September 13.

Organization

Time and Place: Tuesday and Thursday, 1:00 -- 2:20 pm. DC 2568.

Credit:

• 6 small assignments (1 or 2 questions each) (50%)
• a project (50%). Pick some topic that interests you and is relevant to the course; explore some aspect of it; read a few papers; and survey them. You must do a written report and a class presentation. I will suggest possible topics. NEW: Project deatils available above.

Assignments

Course Outline

Topics:

• polygon triangulation
• convex hulls
• Voronoi diagrams and Delaunay triangulations
• arrangements and duality
• linear programming
• geometric data structures, search problems
• motion planning, shortest paths

Books

• [CG] Computational Geometry: Algorithms and Applications, (third edition) M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Springer, 2008.
  There should be copies in the bookstore.
• [CGinC] Computational Geometry in C (second edition), J. O'Rourke, Cambridge University Press 1998.
• [D&CG] Discrete and Computational Geometry, Satyan L. Devadoss and Joseph O'Rourke, Princeton University Press, 2011.

Web Pages

• the computational geometry pages from MathWorld
• CGAL Computational Geometry Algorithms Library
• David Eppstein's Geometry Junkyard and Geometry in Action
• Joseph O'Rourke's comp.graphics.algorithms FAQ
• Graphics Gems

Finding Papers

• Computing Research Repository for Computational Geometry (arXiv)
• Google Scholar
• Computational Geometry journals
  • Discrete and Computational Geometry
  • Computational Geometry Theory and Applications
  • Journal of Computational Geometry
  • International Journal of Computational Geometry
• Computational Geometry conferences
  • Symposium on Computational Geometry
  • Canadian Conference on Computational Geometry
  • European Symposium on Computational Geometry
  • Fall Workshop on Computational Geometry (no proceedings)
• ACM Digital Library

Lectures

Presentation Schedule