Recent applications in geometric computing, such as in computer graphics, computer-aided design (CAD), and structural biology, make use of concepts from topology. The goal of this course is to learn enough topology to see how it applies to geometric computation, and to be able to understand recent publications in this field.
Computational topology is the name of this newly emerging field, that combines the theory of topology with the power of computing to solving problems in diverse fields.
We assume no previous knowledge of topology, but the ability to think in a mathematical way, and of course familiarity with algorithms and programming.
I know very little about computational topology myself, and so in this course we will study this field together, by studying the book "Topology for Computing" by Afra Zomorodian. We can also make use of the notes and slides he prepared for his courses. You should think about this course as a "study group", where students take turns in preparing and presenting part of the material.
Our textbook gives a self-contained presentation of the mathematical concepts from a computer scientist's point of view, combining point set topology, algebraic topology, group theory, differential manifolds, and Morse theory. He also presents some recent advances in the area, including topological persistence and hierarchical Morse complexes. Throughout, the focus is on computational challenges and on presenting algorithms and data structures when appropriate.
A graduate or undergraduate algorithms course (such as CS300 or CS500, or an undergraduate algorithms course you took before coming to KAIST). Computational geometry is recommended.
The class meets Mondays and Wednesdays from 13:00 to 14:30. Presentations are given in English.
The dates in the following table are tentative--be prepared for changes!
| 09-06 | Introduction | |
| 09-18 | Spaces and Filtrations I | Jung Gun |
| 09-20 | Spaces and Filtrations II | Jung Gun |
| 09-25 | Group Theory I | Jooyoung |
| 09-27 | Group Theory II | Jooyoung |
| 10-02 | Homology I | Taek Gyu |
| 10-09 | Homology II | Taek Gyu |
| 10-11 | Morse Theory | Chun-Seok |
| 10-30 | Persistence & Hierchical Morse-Smale Complexes I | Jeong-Hyeon & Youngjun |
| 11-01 | Persistence & Hierchical Morse-Smale Complexes II | Jeong-Hyeon & Youngjun |
| 11-06 | Persistence algorithm I | Janghwan |
| 11-08 | Persistence algorithm I | Hasan |
| 11-13 | The Borsuk-Ulam theorem I | Mira |
| 11-15 | The Borsuk-Ulam theorem II | Mira |
| 11-20 | Tucker's Lemma | Hyo-Sil |
| 11-22 | Applications of Borsuk-Ulam | Hyo-Sil |
| 11-27 | Topological simplification I | Kwangsu & Heejung |
| 11-29 | Topological simplification II | Kwangsu & Heejung |
| 12-04 | Morse-Smale Complex algorithm I | Shinhaeng |
| 12-06 | Alpha-shapes I | Sang-yun |
| 12-11 | Alpha-shapes I | Sang-yun |
Students will be be graded on their presentation and participation in the discussions.
We will be using the book Topology for Computing (second edition), by Afra Zomorodian, Cambridge University Press, 2005.
We can also make use of the slides and notes he prepared for his courses.
Please check the bulletin board regularly for announcements. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)