308-507A Computational Geometry

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

September 2 to December 2, 1999

Course: Computer Science 308-507A
Title: Computational Geometry (3 credits, 3 hours)
Time & Place: TTH 10:00-11:30 in Burnside Hall Room 1B23
Instructor: Godfried Toussaint, Room 307, McConnell
Phone: External - 398-7077, Internal - 5911
Office hours: Tues & Thurs, 16:00-17:00.
Teaching Assistant: Mike Soss; e-mail: soss@cs.mcgill.ca; tel: 398-5931; Office: McConnell 204N; Office Hours: Wednesdays 10:00-12:00 or by appointment.
Course prerequisites:

• 308-405 (Algorithms) or co-requisite 308-506, 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:

• One in-class test at 20% (mid-term).
• One in-class test at 10% (last day of class).
• Five assignments at 10% each.
• One Web project at a total of 20%. The Web project involves publishing a tutorial introduction to a simple idea and is divided into two parts: the HTML document (counts for 8%) and the interactive Java applet (counts for 12%). The HTML document is due October 21. The Java applet is due December 2nd and the entire finished project must be installed in the Computational Geometry Laboratory by that date.

Text book and materials:

• 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 Contents:
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.