COMP 7750 - Fall 2015

COMP 7750 - Computational Geometry

COMP 7750: A graduate course in computational geometry: the design and analysis of efficient algorithms for geometric problems.

instructor: Steph Durocher
office hour: Monday at 9:30 am and Tuesday at 10:30 am in EITC E2-412.

lectures: Monday and Wednesday 10:30 am to 11:45 am in EITC E2-350.

This calendar lists course-related events for COMP 7750:

Although also numbered COMP 7750, this course on computational differs from COMP 7750: Graph Drawing and COMP 7750: Graph Theory. Students who have completed Graph Drawing or Graph Theory for credit can take COMP 7750 (Computational Geometry) for credit.

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.

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
  • point-line duality
See this course outline for a more detailed course description.

Announcements

The final exam will be held from 10:30 am - 12:00 pm on Wednesday December 16 in EITC E2-350.

Project Schedule

last updated December 9, 2015

Important Dates

Dec 2, 7, 9project presentations
Dec 9classes end
Dec 9project report due
Dec 16final exam