# Computational topology

### From CYPHYNETS

Reading group, Winter 2008

Organizer: Abubakr Muhammad

Time: Wednesday at 4:15pm

Venue: McConnell Bldg. Room 321 (SOCS Lounge)

**What is Computational Topology?**

In recent years, there has been an enormous interest among researchers in various disciplines to develop and use topological methods for solving various problems in science and engineering. These algorithmic methods provide robust measures for global qualitative features of geometric and combinatorial objects that are relatively insensitive to local details. This makes topological abstractions into useful models for understanding qualitative geometric and combinatorial questions in several settings. The abstract machinery of algebraic topology has been used in various contexts related to data analysis, object recognition, discrete & computational geometry and distributed computing.

**Summary of Objectives & Activities**

The aim of this reading group is to communicate some of these recent developments to the participants with a minimal background in algebraic topology. Our focus will be on applications, although the proper appreciation of this research will require the understanding of some sophisticated mathematical methods.

Since it is expected that the attendees will come from diverse backgrounds in science, mathematics and engineering; the organizer will provide tutorials on the required background in topology. Moreover, the organizer will demonstrate how to use various computational topology software tools. The majority of meetings will be dedicated to discussing various research articles written by the leading experts in the field. Hopefully, these activities will enable the participants to generate new mathematics as well as new applications.

**Topics**

**Mathematics**: Homology, homotopy, Morse theory, Conley index theory, configuration spaces

**Computational Methods**: Cech-, Rips-, witness- and alpha-complexes, persistent homology of filtrations, harmonic methods for computing homology, software tools.

**Applications**: Coordination, navigation and reconfiguration in robotics, coverage and routing in sensor networks, visualization and qualitative analysis of high-dimensional data sets, analysis of nonlinear dynamical systems, structural biology, image classification, distributed algorithms.

**Who should attend?**

- Mathematicians with interest in topology, geometry and dynamical systems
- Computer scientists investigating computational geometry, machine learning, visualization & data analysis
- Engineers interested in algorithmic aspects of robotics, networked sensing and control theory
- Life scientists dealing with large data sets in molecular biology, neuroscience, systems biology.

DATE | TOPICS | FRONTIERS | SUGGESTED READINGS |
---|---|---|---|

Background | |||

Jan 16 | Overview of computational topology | . | Bar codes: The persistent topology of data by Robert Ghrist. |

Jan 23 | Simplicial & cubical complexes, homotopy | Math | Notes on homology theory by Abubakr Muhammad.
Also check Afra Zomorodian's course notes. |

Feb06 | Homotopy; Simplicial Homology | Math, CS | Same as last week. |

Feb13 | Filtrations & persistent homology | Math,CS | Computing Persistent Homology by Zomorodian ad Carlsson. |

Feb 20 | Hands-on training. Plex Software Package | CS | |

Data Analysis, Learning & Visualisation | |||

March05 | Manifold Learning from point cloud data sets(PCD) | Math,CS,Bio | Fiding the homology of submanifolds with high confidence from random samples by Nitogi, Smale and Weinberger. |

March 12 | Persistence and its Stability in PCDs | Math,CS,Bio | Persistent Homology - a Survey by Herbert Edelsbrunner and John Harer. |

April02 | Natural Image Classification | EE,CS,Bio | A topological Analysis of the Space of Natural Images by Gunnar Carlsson and Tigran Ishkanov. |

April 09 | Homology computation using harmonic analysis | CS, Math | Computing Betti numbers via |Combinatorial Laplacians by Joel Friedman. |

Network and Sensing | |||

Coverage problems in sensor networks -I | EE,CS | Homological sensor networks by deSilva and Ghrist( survey). Blind swarms for coverage in 2D by Ghrist, deSilva, Muhammad. | |

Coverage problems in sensor networks -II | EE,CS | Coordinate-free coverage in sensor networks with controlled boundaries via homology by DeSilva and Ghrist. | |

Landmarks,routing and homology feature size in sensor networks | EE,CS | Geodesic Delaunay Triangulation and Witness Complex in the Plane by Gao, Guibas, Oudot, and Wang. | |

Robotics and Coordination | |||

Morse theory - continuous, discrete & combinatorial | Math | ||

Navigation in robotics | EE,ME,CS | ||

Configuration Spaces-I: Distributed coordination | Math,ME,EE | ||

Configuration spaces-II: Reconfigurable systems | Math,ME,EE | ||

Dynamical Systems | |||

Conley index theory | Math | ||

Computer assisted proofs in dynamical systems | Math,Phys,Bio | ||

Hands-on Training: CHomP software package | Math,CS | ||

Miscellaneous Topics | |||

Topology of random data and random fields | Math,CS | ||

Protein docking and structural biology | Bio,CS |

**Resources in Computational Algebriac Topology**

**Workshops/Programs**

- 2006 MSRI Workshop on Application of Topology in Science and Engineering.
- 2004 IMA Short Course Computational Topology.
- Topological Methods in Scientific Computing, Statistics and Computer Science, Stanford University
- Computational Homology Project, CHomP
- DARPA-DSO program in fundamental mathematics: Sensor Topology for Minimal Planning
- DARPA-DSO program in fundamental mathematics: Topological Data Analysis
- 2007 TTI Workshop on Geometric and Topological Approaches to Data Analysis
- 2008 International Workshop on Algorithmic Topology, Bellairs-McGill
- Workshop on Topology learning, NIPS 2007.

**Courses**

- Computational topology by Prof Edulsbrunner at Duke
- Computational topology and geometry by Prof Yap at NYU
- Introduction to computational topology by Prof Zomorodian at Dartmouth
- Computational dynamics and topology by Prof Day at William & Mary
- Topology for computing by Profs Cheong & Choi at KAIST
- Computational topology seminar, by Profs Giesen and Sagraloff, Max Planck Institute

**Software**

- Plex (Stanford)
- Computational Homology Project, CHomP

**Books**

- Tomasz Kaczynski, Konstantin Mischaikow, Marian Mrozek (2004), Computational Homology, Springer, ISBN 0-387-40853-3.
- Afra J. Zomorodian (2005). Topology for Computing, Cambridge, ISBN 0-521-83666-2.
- William Brasener (2006), Topology and its applications, John Wiley, ISBN: 978-0-471-68755-9.
- Allen Hatcher,Algebraic Topology.