Computational topology

From CYPHYNETS

Jump to: navigation, search

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.


Tentative Schedule
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

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

Courses

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

Software

  1. Plex (Stanford)
  2. Computational Homology Project, CHomP

Books

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