CISC-868: Computational Geometry

(Fall 2011)

Last Modified:

Shortcut to the homework assignments.

Important Announcement

There will be an additional class on Dec. 5. The format of that class will be (your) questions and (your and my) answers for the purpose of preparing for the final test. The final test will be held on Dec. 12. Both the class and the test will be in our classroom at our normal time, 4:00 - 7:00.

Course Instructor

David Rappaport
E-MAIL: daver AT cs dot queensu dot ca
Contact: after class or by e-mail appointment

Class Hours

Monday 4:00-7:00

Required Text

I will closely follow the text book
Satyan L. Devadoss & Joseph O'Rourke
Discrete and Computational Geometry
It is available in print and electronic form at in print (at a lower price) at and for 180 day digital rental (even lower in price) at CourseSmart.

Supplementary Reading

The following book has been a standard computational geometry text since it was first published more than 10 years ago. It is somewhat more technical than the required text. It is available for free in electronic form courtesy of the Queen's Library
Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars
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. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani

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

Course Description

Computational geometry is the study of the design and analysis of computer algorithms for geometric problems. In this course fundamental algorithms in computational geometry will be covered. A background in the design and analysis of algorithms is assumed (such as the Queen's course CISC-365). Nevertheless, I will also be covering basic concepts using the book Algorithms cited above.

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

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.


Grades will be assigned for doing homework assignments, presenting solutions to homework assignments in class, submitting written project and a final exam. The details of the precise marking scheme will be a function of the class; its size as well as the background and temperament of its constituents.
A good starting point for the mark breakdown which might be modified with the class approval is as follows.
Homework Assignments50%
Written Project25%
Final Exam25%

Academic Intergrity

On October 23, 2008 Queen's University Senate approved its policy on "Academic Integrity Procedures -Requirements of Faculties and Schools". The "AI Policy" takes effect immediately and replaces the 1989 Senate Policy on "Academic Dishonesty". The policy can be found on the Senate Policy web page at:
A statement by the School of Graduate Studies on academic integrity can be found at:

In this course you may use what I will call limited collaboration. You can get together in groups to brainstorm on the homework problems. However, when it comes to putting things down on paper (or in bits) then you are required to do this by yourself. As a courtesy to your collaborators you should explicitly acknowledge those who have helped and the nature of their help. For example: "I acknowledge A for useful discussions." or, "The main ideas behind my solution are due to B."

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.


week 10


Project instructions PDF.
Zip file with LaTeX source of the project instructions.


Homework 1.
Homework 2.
Homework 3.
Homework 4.
Homework 5.
Homework 6.
Homework 7.
Homework 8.
Homework 9.
Homework 10.