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
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
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 Amazon.com in print (at a lower price) at Amazon.ca 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 Algorithms.
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:
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.
Grading
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.
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.