Pre-requisites : CS204 Algorithms or equivalent
This course is a combination of Algorithms, Geometry, and Topology. The course starts with a broad introduction to basic notions in Topology for a Computer Scientist. Then it primarily focuses on designing efficient Algorithms and data structures for the problems from Topology. The relevant topics ranging from point set topology to algebraic topology are presented. The course is motivated with the applications from computational structural biology, geometric modeling, meshing, curve and surface reconstruction, clustering, 3d-printing, orthodontics, and VLSI routing.Introduction to topological spaces with motivating examples Geometric topology: searching a triangulation, surface simplification, triangulations, and complexes Manifolds: homeomorphism, Jordan separation Theorem, Conway's ZIP proof, imbedding graphs in the plane, and Euler characteristics Homotopy: deformation retraction, topological equivalence, categories, functors, homotopic paths in the plane, and homotopy of curves on surfaces Topological Graph Theory: Connected components in surface graphs, min-cuts in surface graphs, and tree decomposition designing algorithms based on Homology and Duality Theories.
1. H. Edelsbrunner, Computational Topology, 1st Edn., American Mathematical Society, 2010.
2. J. R. Munkres, Topology, 2nd Edn., Prentice Hall, 2000.
1. Artin, Algebra, 2nd Edn., Addison Wesley, 2010.
2. B. Mendelson, Introduction to Topology, 3rd Edn., Dover Publications Inc., 1990.
3. M. A. Armstrong, Basic Topology, Springer, 2010.
4. A. Hatcher, Algebraic Topology, 1st Edn., Cambridge University Press, 2001.
5. Y. Matsumoto, An Introduction to Morse Theory, 1st Edn., American Mathematical Society, 2001.