COMP 7922  Computational Geometry
COMP 7922:
A graduate course in computational geometry:
the design and analysis of efficient algorithms for geometric problems.
instructor: Steph
Durocher
office hour: Tuesday at 10:30 am in EITC E2412.
lectures: Tuesday and Thursday 11:30 am to 12:45 pm in EITC E2164.
This calendar lists courserelated events for COMP 7922:
Prerequisites
Students are expected to have a strong background in theoretical computer
science (e.g., A or A+ in COMP 3170).
Students will be required to complete a mandatory quiz during the first week
of classes to help determine whether they possess the required background.
Quiz marks will not count towards course grades, but students are required
to pass the quiz to continue in the course.
There is no need to study any specific material before the quiz.
The formal course requirements are:

an upperlevel undergraduate course in algorithms
analysis and data structures
such as COMP 3170

a course in discrete mathematics
such as COMP 2130
Textbook
Computational Geometry:
Algorithms and Applications, third edition
by de Berg, Cheong, van Kreveld, and Overmars,
SpringerVerlag 2008.
The textbook is available from
the University of Manitoba
bookstore.
Another helpful reference is:
Discrete and Computational
Geometry
by Devadoss and O'Rourke,
Princeton University
Press 2011.
A useful reference for reviewing prerequisite material is:
Introduction
to Algorithms, third edition, by Cormen, Leiserson, Rivest, and Stein,
MIT Press 2009.
(umanitoba ebook
link)
Topics Covered
Topics will include a subset of:
 convex hulls
 point location
 Voronoi diagrams and Delaunay triangulations
 range searching
 geometric intersection
 kinetic data structures
 arrangements of lines and circles
 unit disc graphs and proximity graphs
 smallest enclosing discs, width, and diameter
 facility location
 guarding, art galleries, and visibility graphs
 geometric packing and covering
 pointline duality
See this course outline for
a more detailed course description.
