Department of Computer Science

CPSC 516: Computational Geometry & Graph Drawing -- Spring 2013


Instructors: Will Evans & David Kirkpatrick

Contacts (Evans): ICICS/CS x841 (office); 604-822-0827 (phone); will@cs.ubc.ca (email)

Contacts (Kirkpatrick): ICICS/CS x839 (offoce); 604-822-4777 (phone); kirk@cs.ubc.ca (email)

Lecture times: Monday and Wednesday, 14:00-15:30, DMPT 101

******** Extra Lecture time: Tuesday, March 12, 16:45-18:00, ICICS/CS 206 ********

Prerequisites: Graduate standing or consent of instructor. Students are expected to be familiar with the basic (senior undergraduate level) concepts in algorithm design (such as divide-and-conquer, greedy algorithms, dynamic programming, randomized algorithms) and analysis (such as solving recurrences, basic probability theory, and amortized analysis), as well as basic data structures (such as heaps, hash tables and balanced trees).

Course Objectives: This is an advanced course on algorithm and data structure design and analysis, with a focus on problems in discrete and combinatorial geometry. Emphasis will be placed on the development of general design and analysis techniques and data structures that are tailored to (particularly, low-dimensional) fundamental computational problems in discrete geometry, including geometric optimization, search, proximity, intersection, decomposition, visibility and mobility problems.
In this year's offering we will pay particular attention to the interplay between abstract graphs and their realization as geometrically-constrained embeddings (drawings), focusing on both characterizations of graphs that can be realized and methods to achieve satisfactory realizations.
Though they will not be the primary focus of our discussion, applications in a variety of areas, including geographic information systems, computer graphics, robotics, computer aided design and manufacturing, and mesh generation, will be mentioned; many of these constitute potential topics for course projects.
(Most of the problems that we encounter are easy to visualize, and solutions often arise from geometric intuition; problem solving in this domain is fun!)

Course Materials:
We will make frequent reference to the text: Computational Geometry: Algorithms and Applications, Third Edition (March 2008), by M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, published by Springer-Verlag. ( BCKO ) This will be supplemented by material drawn from other texts and from recent journal/conference papers.
We will also make extensive use of the excellent lecture notes prepared by David Mount for his graduate course at the University of Maryland ( MountNotes2012 ). A substantial amount of other material, including notes and visualizations, is available elsewhere on the web (see below).

Some Useful Links:

Evaluation: There will be a small number (3-4) of homework assignments, one exam covering core material (approximately the first 9 weeks of lectures), and a project (that might involve design and analysis of a new algorithm, a survey of existing algorithms for some problem, emperical evaluation and comparison of several algorithms, or application of computational geometry techniques to problems arising in some related application domain). It is expected that students will be actively engaged in the discussion, and to a limited extent, the presentation of lecture material. Approximate evaluation scheme: 25% assignments, 35% exam, 35% project, 5% instructor's discretion (including class participation).

Outline of Topics: A list of topics (more than we will be able to cover completely appears here: TopicList

Assignments: All assignments will be posted here.