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 surveys and textbooks. Key references for the course are hilighted. 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
- Marshall Bern, David Eppstein, and 20 others. Emerging challenges in computational topology. arXiv:cs/99099001, 1999.
[A white paper from an NSF-sponsored workshop; biased toward computational geometry.]
- Tamal K. Dey, Herbert Edelsbrunner, and Sumanta Guha. Computational topology. Advances in Discrete and Computational Geometry (Bernard Chazelle, Jacob E. Goodman and Richard Pollack, editors), pp. 109–143. Contemporary Mathematics 223, American Mathematical Society, 1999.
[Good survey of the state of the art ten years ago; somewhat biased toward computational geometry.]
- Nathan Dunfield, editor. The CompuTop.org Software Archive. Last updated July 25, 2009.
[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.
[Not yet in print, but a draft of the table of contents and first three chapters is (perhaps unintentionally) available online.]
-
Helwig Hauser, Hans Hagen, and Holger Theisel, editors. Topology-based Methods in Visualization. Mathematics and Visualization, Springer, 2007.
[Proceedings of a 2005 workshop, primarily focused on the visualization of vector fields.]
-
Joel Hass. Algorithms for recognizing knots and 3-manifolds.
arXiv:math/9712269, 1999.
-
Hans-Christian Hege, Konrad Polthier, and Gerik Scheuermann, editors. Topology-based Methods in Visualization II. Mathematics and Visualization, Springer, 2009.
[Proceedings of a 2007 workshop, primarily focused on the visualization of vector fields.]
- 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.]
- T. J. Peters, J. Bisceglio, D. R. Ferguson, C. M. Hoffmann, T. Maekawa, N. M. Patrikalakis, T. Sakkalis, and N. F. Stewart. Computational Topology for Regular Closed Sets (Within the I-TANGO Project). Topology Atlas Invited Contributions 9(1), 2004.
[Emphasizes topological subtleties arising from intersecting and approximating geometric objects, especially in CAD systems.]
-
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.