CS-507A: Computational Geometry

Course prerequisites:

• 308-360 (Algorithms) or:
• Knowledge of design and analysis of algorithms ("Big O" notation, etc.)
• Knowledge of data structures (stacks, linked-lists, arrays, balanced trees, etc.)
• Knowledge of probability and statistics.

Performance assessment:

• Two in-class 75-minute tests at 24% each (after 4 and 9 weeks approximately).
• One oral in-class presentation on the theory behind the web project at 20% (at the end of term).
• One Web project at a total of 32%. The Web project involves publishing a tutorial introduction to a simple idea and is divided into two parts: the HTML document (counts for 12%) and the interactive Java applet (counts for 20%). Both the HTML document and the Java applet are due December 3rd and the entire finished project must be installed in the Computational Geometry Laboratory by that date.
• About five practice assignments (not collected, not marked, and not counted). However, students who wish may hand in their assignments to the TA's for feedback. The TA will give tutorials on these as necessary.

Text book and materials:

• Mark de Berg, et al., Computational Geometry: Algorithms and Applications, Springer Verlag, 1997.
• In-class handouts (technical reports and reprints) on topics not in the text.
• Reading material on the web

Useful books:

• J. O'Rourke, Computational Geometry in C, Second Edition, Cambridge University Press, 1998.
• Franco P. Preparata and Michael I. Shamos, Computational Geometry, Springer-Verlag, 1985.
• J. E. Goodman and J. O'Rourke, Eds., Handbook of Discrete and Computational Geometry, CRC Press, Boca Raton, 1997.

Topics:

• Convex hulls, polygons, Voronoi diagrams and Delaunay triangulations, arrangements, plane sweep, duality, geometric optimization, linear programming, range searching and point location, decomposition and partitioning, geometric data structures...