Topics in Computation Theory (CS700)

Topology for Computing

Fall Semester 2006

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.


Otfried Cheong (Office: E3-1 3434, Phone: 3542) and Sunghee Choi (Office: E3-1 3430, Phone: 3534).


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

Grading policy

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.

Bulletin board

Please check the bulletin board regularly for announcements. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)

Otfried Cheong