Introduction to Computational Topology

COSC 49.09, Fall 2020

Main | Schedule | Homeworks | About

About the course

Topology is the art of studying shapes without precise measurements. It is not surprising then that topology has found many applications in computer science, both in theoretical and applied research including algorithms and complexity theory, data analysis, robotics, computer graphics, etc., where often the input data is geometrically constrained, or noisy due to measurement errors. The course serves as an introduction to the rapidly growing area(s) of computational topology.

Students are assumed to have reasonable math maturity, in particular the ability to read and write proofs. COSC 30: Discrete Math or equivalent is required as prerequisite. Experience in the analysis of algorithms (COSC 31: Algorithms) is strongly recommended but not required. Previous exposure in linear algebra and graph theory will also help. Background in general topology (the study of topological spaces) is not required.

MATH 74: Algebraic Topology (last offered in Spring 2020) is a more rigorous treatment of the mathematical theory behind computational topology. We will focus more on the applications in computer science and not always give full proofs to the results. For students who took MATH 74 before or are familiar with the language of topology will benefit by seeing how the concepts are applied in computer science.

Textbook and References

There is no required textbook. We will use a mix of books and class notes (and sometimes papers) as references; none of them covers the exact set of topics we will talk about. The relevant reading materials will be emphasized on the schedule page each week for the interested students to read in their off-time.

Here is a list of books and lecture notes on computational topology. Not all of them are relevant to this course, but I find them helpful in my study.

Jean-Daniel Boissonnat and Monique Teillaud, Effective Computational Geometry for Curves and Surfaces
Éric Colin de Verdière, Algorithms for Embedded Graphs
Keenan Crane, Discrete Differential Geometry: An Applied Introduction
Herbert Edelsbrunner and John Harer, Computational Topology — An Introduction
Herbert Edelsbrunner, A Short Course in Computational Geometry and Topology
Robert Ghrist, Elementary Applied Topology
Allen Hatcher, Algebraic Topology
Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum, Distributed Computing Through Combinatorial Topology
Philip Klein and Shay Mozes, Optimization Algorithms for Planar Graphs
Dmitry Kozlov, Combinatorial Algebraic Topology
Francis Lazarus and Arnaud de Mesmay, Computational Topology: Lecture notes
Jiří Matoušek, Using the Borsuk-Ulam Theorem
James Munkres, Topology
John Stillwell, Classical Topology and Combinatorial Group Theory
Afra Zomorodian, Topology for Computing

Related Courses

Here is a list of similar/related courses offered by other instructors, sorted into several (arbitrarily decided) categories according to their flavors. Again I'll emphasize that the classification is arbitrary and all by me; in particular the instructors of these courses might not agree with me.