COMP 7750/4060 - Computational Geometry
COMP 7750:
A graduate course in computational geometry.
This course is co-listed as COMP 4060.
instructor: Steph
Durocher
office hour: Tuesday and Thursday, 3:45 pm - 4:30 pm in EITC E2-412.
lectures: Tuesday and Thursday, 10:00 am - 11:15 am in EITC E2-461.
This calendar lists course-related events for COMP 7750:
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 upper-level 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,
Springer-Verlag 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.
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
- point-line duality
|