**COMP-507A:
Computational Geometry**

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

- 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.*

- 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.

- 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*.

- 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.

- 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.

- 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).