Introduction to Computational Topology

COSC 249.09, Fall 2021

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. This graduate-level course serves as an introduction to the rapidly growing area(s) of computational topology, from a theoretical point of view. Naturally, due to the vast amount of work and literature in the area, the topics covered in this class will be biased towards the interest and expertise of the instructor.

Course Objectives

By the end of the course we expect the students to be able to read articles and follow the basic terminology required to conduct research in computational topology. Also, we hope that the students enjoy the beauty of topology and have fun with the puzzles offered.

Prerequisite

Students are assumed to have reasonable math maturity, in particular the ability to read and write proofs. A proof-based course like COSC 30 Discrete Mathematics or equivalent is required as prerequisite. Experience in the analysis of algorithms (say COSC 31: algorithms) is strongly recommended. Previous exposure in linear algebra (like MATH 24 or COSC 70) and graph theory (like MATH 38) will also help. We will hand out homework 0 in the first week and give the students an idea of the background knowledge expected. Background in general topology (the study of topological spaces) is not required.

Related Courses

MATH 32: The Shape of Space (syllabus for Winter 2020) is an undergrad-level course on geometry and topology (a descendant of the legendary course "Geometry and the Imagination" at Princeton by Thurston, Doyle, Conway, and Gilman), covering a subset of the topics we offered in this class. The course put emphasis on the process of thinking about mathematics, not in acquiring as much knowledge as possible. The students get to play with materials like Legos, mirrors, scissors, papers, and keeping a research journal while frequently discussing with other students.
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
Tamal Dey and Yusu Wang, Computational Topology for Data Analysis
H. Edelsbrunner and J. L. Harer, Computational Topology — An Introduction
H. Edelsbrunner, A Short Course in Computational Geometry and Topology
R. 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 R. Munkres, Topology
Vidit Nanda, Computational Algebraic 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.

Computational/Applied Topology

Computational Topology by Herbert Edelsbrunner
Computational (Geometry and) Topology by Brittany Terese Fasy
Computational Topology by John Hughes

Computational Algebraic Topology

These courses tend to focus on the development of algebraic topology machinery behind the applications.

Introduction to Computational Topology by Bala Krishnamoorthy
Computational Algebraic Topology by Vidit Nanda
MATH 496/696 (Spring 2016) by Michael Robinson
Computational Algebraic Topology by Ulrike Tillmann

Discrete Differential Geometry

Discrete Differential Geometry by Graphics Group at Columbia University
Discrete Differential Geometry: An Applied Introduction by Keenan Crane
Advanced Topics in Computer Graphics: Discrete Differential Geometry by Misha Kazhdan

Topological Data Analysis

Applied Topology by Henry Adams
Computational Topology and Data Analysis by Tamal K. Dey
Topology and Its Applications by Chad Giusti
Topological Data Analysis by Steve Oudot
Topological Data Analysis: The New Frontier of Data Science by Bei Wang Phillips
Computational topology: Theory, algorithms, and applications to data analysis by Yusu Wang

Complexity of Topological Problems

Computational Topology by Francis Lazarus and Arnaud de Mesmay

Optimization on Surfaces

Algorithms for Planar Graphs and Beyond by Erik Demaine, Shay Mozes, Christian Sommer, and Siamak Tazari
One-Dimensional Computational Topology by Jeff Erickson
Recent Advances in Computing — Computational Topology by Kyle Fox
Optimization Algorithms for Planar Graphs by Philip Klein
Algorithms for Planar Graphs by Shay Mozes

Combinatorial Topology

Including topological graph theory and topological methods in combinatorics.

Topological Graph Theory by Jeff Hicks
Topics in Combinatorial Topology by D. Yogeshwaran

Applications in CS

Minicourse: Algebraic and Differential Topology in Data Analysis by Yuliy Baryshnikov
Topics in Topology: Scientific and Engineering Applications of Algebraic Topology by Isabel K. Darcy
Topological Robotics by Michael Farber
Distributed Computing through Combinatorial Topology by Maurice Herlihy
Mesh Generation and Geometry Processing in Graphics, Engineering, and Modeling by Jonathan Shewchuk

Religious Observances

Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me as soon as possible, or before the end of the second week of the term—at the latest, to discuss appropriate adjustments.

COVID-19 Information

Attendance

For the health and safety of our class community, please: do not attend class when you are sick, nor when you have been instructed by Student Health Services to stay home. You will be able to view recordings of class in Canvas if you are unable to attend.

Safety

In accordance with current College policy, all members of the Dartmouth community are required to wear a suitable face covering when indoors, regardless of vaccination status. This includes our classroom and other course-related locations, such as labs, studios, and office hours. If you need to take a quick drink during class, please dip your mask briefly for each sip. Eating is never permitted in the classroom. (The only exception to the mask requirement is for students with an approved disability-related accommodation; see below.) If you do not have an accommodation and refuse to comply with masking or other safety protocols, I am obligated to assure that the Covid health and safety standards are followed, and you will be asked to leave the classroom. If you refuse to comply with masking or other safety protocols, and to ensure the health and safety of our community, I am obligated to report you to the Dean’s office for disciplinary action under Dartmouth’s Standards of Conduct. Additional COVID-19 protocols may emerge. Pay attention to emails from the senior administrators at the College.

Accessibility Services

Students requesting disability-related accommodations and services for this course are encouraged to schedule a meeting with me as early in the term as possible. This conversation will help to establish how your accommodations will be implemented in my course and what role Student Accessibility Services (SAS) or its Testing Center may play in assisting. In order for accommodations to be authorized, students are required to register with SAS (Getting Started with SAS webpage; student.accessibility.services@dartmouth.edu; 603-646-9900) and to request an accommodation email be sent to me in advance of the need for an accommodation. If students have questions about whether they are eligible for accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.

last modified on