CS-507A: Computational Geometry

COMP-507A: Computational Geometry

"Where there is matter, there is geometry." - Johannes Kepler

Course: Computer Science COMP-507
Title: Computational Geometry (3 credits, 3 hours)
Time & Place:
Instructor: Godfried Toussaint
Phone:
Office hours:
Teaching Assistant:

Course prerequisites:

COMP-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 of an approved journal paper, 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 November 29 and the entire finished project must be installed in the Computational Geometry Lab by that date.
Four or 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. Solutions will be handed out on the "due" dates.

Text book and course material:

J. O'Rourke, Computational Geometry in C, Second Edition , Cambridge University Press, 1998.
In-class handouts (technical reports and reprints) on topics not in the text.
Reading material on the World Wide Web course page.

Useful books:

Mark de Berg, et al., Computational Geometry: Algorithms and Applications, Springer Verlag, 1997.
Franco P. Preparata and Michael I. Shamos, Computational Geometry , Springer-Verlag, 1985.
J. O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987.
G. T. Toussaint, Ed., Computational Geometry, North-Holland, 1985.
G. T. Toussaint, Ed., Computational Morphology, North-Holland, 1988.
J. E. Goodman and J. O'Rourke, Eds., Handbook of Discrete and Computational Geometry, CRC Press, Boca Raton, 1997.
Ming C. Lin and Dinesh Manocha, (Eds.), Applied Computational Geometry, Springer-Verlag, 1996.

Course Outline:

Classical geometry and basic concepts. Ancient and modern models of geometric computation. Point inclusion problems. Convexity testing. Computing and updating triangulations of polygons, sets of line segments and sets of points. Computing distances between sets. Art-gallery theorems. Relationships between computational complexity, unimodality of functions and convexity. Computing convex hulls of polygons and point sets. Hidden line problems. Proximity graphs and their applications. Facility location and linear programming. Mobility of objects in space. Removing non-degeneracy assumptions. Computing shortest transversals of sets. Arrangements of lines and their applications. Visualization via nice projections.

Reminder:

McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see www.mcgill.ca/integrity for more information).