CS 598: Computational Topology (Fall 2009)
References
There is no required textbook for this class; I will post electronic copies of relevant papers to this web site as the course progresses. Meanwhile, here is a list of background references, primarily textbooks and recent surveys. Key references for the course are highlighted. Many of the other references focus on material that we will not cover at all in the course; I include them primarily to give some sense of the diversity of the field.
Computational topology
- Nathan Dunfield, editor. The CompuTop.org Software Archive.
[A collection of links to software for low-dimensional topology, especially 3-manifolds.]
- Herbert Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge University Press, 2001.
[Emphasizes mesh generation and simplification; includes a thorough survey of combinatorial topology.]
- Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. AMS Press, 2009.
- Tomasz Kaczynski, Konstantin Mischaikow, and Marian Mrozek. Computational Homology. Applied Mathematical Sciences 157, Springer, 2004.
[What it says on the tin; emphasizes the homology of cube complexes. The algorithms are implemented as part of the CHomP project.]
- Sergei Matveev. Algorithmic Topology and Classification of 3-Manifolds. 2nd edition, Springer, 2007.
[Emphasizes 3-manifold computation, building up to an algorithm for recognizing of Haken 3-manifolds via normal surface theory.]
-
Sanjay Rama, edtior.
Topological Data Structures for Surfaces: An Introduction to Geographical Information Science. Wiley, 2005.
[Emphasizes data structures for geographic information systems.]
-
Günter Rote and Gert Vegter.
Computational topology: an introduction. Chapter 7 of
Effective Computational Geometry for Curves and Surfaces (Jean-Daniel Boissonnat and Monique Teillaud, editors), pp. 277–312. Mathematics and Visualization, Springer-Verlag, 2006.
[A survey of combinatorial (not really computational) topology, emphasizing simplicial homology and Morse theory.]
-
Afra Zomorodian. Topology for Computing. Cambridge Monographs on Applied and Computational Mathematics 16. Cambridge University Press, 2005.
[Emphasizes persistent homology and Morse theory.]
Topology
Topological graph theory
Algorithms
-
Mark de Berg,
Otfried Cheong,
Marc van Kreveld, and
Mark Overmars.
Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd edition, 2008.
[The standard reference for computational geometry.]
-
Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, and Clifford Stein.
Introduction to Algorithms. MIT Press/McGraw-Hill, 2001.
-
Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms. McGraw-Hill, 2006.
-
Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2005.
-
Jeff's algorithms notes.