Spring 2013

TuTh 2:00–3:15, 214 Ceramics

- Welcome! The schedule and notes from the Fall 2009 iteration of this course are still available.

Computational topology is an emerging field of study at the intersection of mathematics and computer science, devoted to the study of efficient algorithms for topological problems, especially those that arise in other areas of computing. Although algorithmic techniques have been ubiquitous in topology since its inception more than a century ago, the efficiency of topological algorithms and their applicability to other computing domains are relatively recent areas of study. Results in computational topology combine classical mathematical techniques from combinatorial, geometric, and algebraic topology with more recent algorithmic tools from data structure design and computational geometry. These results have found applications in many different areas of computer science.

This course will be a broad introduction to computational topology; the precise topics covered will depend on the skills and interests of the course participants. Potential mathematical topics include the topology of cell complexes, topological graph theory, homotopy, covering spaces, simplicial homology, persistent homology, discrete Morse theory, discrete differential geometry, and normal surface theory. Potential computing topics include algorithms for computing topological invariants, graphics and geometry processing, mesh generation, curve and surface reconstruction, VLSI routing, motion planning, manifold learning, clustering, image processing, and combinatorial optimization.

Students in all areas of computer science, mathematics, and related disciplines are welcome. CS 573 and/or Math 525 are recommended as prerequisites, but not required; necessary background material will be introduced as needed.

The selection of topics in this class is necessarily limited by the finiteness of a single semester and biased by my own interests and expertise. The full diversity of techniques, results, applications, and even *definitions* of computational topology could easily fill a dozen courses. Here is a sample of some other classes/seminars in computational topology and some closely related fields:

- Otfried Cheong and Sunghee Choi, KAIST (Fall 2006)
- Sarah Day, William and Mary (Spring 2008)
- Herbert Edelsbrunner, Duke University (Fall 2006)
- Joachim Giesen and Michael Sagraloff, Max-Planck-Institut für Informatik (Fall 2006)
- Rob Ghrist, University of Pennsylvania
- Susan Holmes, MSRI (Fall 2006)
- Spike Hughes, Brown (Spring 2011)
- Bala Krishnamoorthy, Washington State (Spring 2012)
- Dmitriy Morozov, Stanford University (Fall 2009)
- Abubakr Muhammad, McGill University (Winter 2008)
- Chee Yap, NYU (Fall 2006)
- Peter Schröder and Keenan Crane, Caltech (Fall 2012)
- Afra Zomorodian, Dartmouth College (Winter 2011)