## CISC-868: Computational Geometry |

## (Fall 2011) |

Last Modified:

GOODWIN HALL Room 532

GORDON HALL Room 425

E-MAIL: daver AT cs dot queensu dot ca

Contact: after class or by e-mail appointment

Monday | 4:00-7:00 |

Discrete and Computational Geometry

Computational Geometry:Algorithms and Applications, Springer Berlin Heidelberg

QCAT - Queen's Library Catalogue.

The next book is a general algorithms text that may be useful to some of you who need to brush up on some basic topics. It too is free in electronic form.

Algorithms.

Please do not clog up shared printers by printing large sections of these books during busy times.

I hope to cover the following topics, as well as other related and/or prerequisite algorithmic concepts:

- convex hull of point sets,

- triangulation, polygon triangulation,

- intersection of line segments,

- Voronoi diagrams,

- line arrangements and geometric duality,

I will motivate these topics through applications. Some of the applications areas that we will see are: geographic informations systems, computer aided manufacturing, database querying, geo-positioning, and computer graphics.

A good starting point for the mark breakdown which might be modified with the class approval is as follows.

Homework Assignments | 50% |

Written Project | 25% |

Final Exam | 25% |

A statement by the School of Graduate Studies on academic integrity can be found at: http://www.queensu.ca/sgs/Currentstudents/policies/academicintegrity.html

In this course you may use what I will call

Cutting and pasting from any external source and passing it off as your own work is expressly forbidden, and will be considered as a departure from academic integrity.