308-507A Computational Geometry

The content of this page is a copy of the teacher's course description.

The current course description

"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:

Performance assessment:

Text book and materials:

Useful books:

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.