An Overview of Computational Topology

Computational topology is an emerging area at the intersection of math and computer science, growing from the increasing need for algorithmic computation that is rooted in the tools and techniques of topology. Specific topics we plan to cover include topological data analysis and persistent homology, surface reconstruction, 3-manifold algorithms, graphs on surface, and higher dimensional algorithmic and hardness results. A familiarity with either topology or algorithms recommended, but the level is geared for graduates students in either mathematics or computer science, and necessary background will be introduced along the way.

The schedule below will be updated as the semester progresses, including slides or any useful associated reading.

Week 1:Tuesday, 9/5Speaker: David Letscher

Title: Topological Data Analysis: History and Challenges

Abstract: Topological Data Analysis (TDA) has it's roots in applied algebraic topology and has grown into a set of tools that have been applied to a wide range of application domains. We will examine the history of TDA and, as it gets used more frequently to study scientific data, the challenges for its use for statistical analysis and prediction. We will also discuss the connections of the methods with algebraic topology, low-dimensional topology and algorithms.

Week 2:Tuesday, 9/12Speaker: Erin Chambers

Title: Tools from computational geometry

Abstract: Computational topology draws on many constructs from computational geometry, a closely allied area whose focus is designing and implementing algorithms to solve geometric problems. In particular, for problems such as surface reconstruction or topological data analysis, we often use the classic computational geometry construction of a Voronoi diagrams (and its dual, the Delaunay triangulations). In this lecture, we will introduce these constructs and their uses. No prior algorithms or computational geometry expertise is needed.

Week 3:Tuesday, 9/19Speaker: Erin Chambers

Title: Reconstructing surfaces from point scans

Abstract: A fundamental problem when representing or analyzing object is the following: given a set of points, generally produced by scanning some object (i.e. in applications such as motion capture, facial recognition, medical imaging, etc.), reconstruct a triangulation on these points which accurately represents the original object. We will survey classical results and algorithms from this area, focusing especially on the crust and powercrust algorithms, which were some of the first to give provable guarantees on the quality of the reconstruction, both from a topological and a geometric standpoint.