University of Minnesota
University of Minnesota
http://www.umn.edu/
IMA Web

2004 IMA New Directions Short Course

Computational Topology

July 6-16, 2004

Logo for the IMA New-Directions Course:
Computational Topology

Principal Speakers

Herbert Edelsbrunner
Computer Science Department
Duke University
edels@cs.duke.edu
http://www.cs.duke.edu/~edels/

John L. Harer
Department of Mathematics
Duke University
john.harer@duke.edu
http://www.math.duke.edu/~harer/

Schedule Participants
Dining Guide Maps
Photo Gallery Feedback

From July 6-16, 2004 the IMA will host an intensive short course designed to efficiently provide mathematicians the basic knowledge prerequisite to understand  "Computational Topology." The course will be taught by Herbert Edelsbrunner, Professor of Computer Science and Mathematics at Duke University and John L. Harer, Professor and Vice Provost for Academic Affairs, Department of Mathematics, Duke University. Participants will receive full travel and lodging support during the workshop.

Content and philosophy. We understand Computational Topology as the development of algorithmic tools implementing topological concepts for use in the sciences and engineering. This is different from using the computer to study topological questions although there is the potential for a beneficial symbiosis between the two efforts. The history of Computational Topology is short. It grew out of Computational Geometry as researchers expanded into applications where significant topological issues arise. The two such areas discussed in this course are structural molecular biology and geometric modeling. Both have connections to industries of substantial economical size.

A primary goal in this course is to develop a broad picture in which algorithmic tools connect pure mathematics with scientific applications. Our utilitarian view is that the application should drive the mathematics, the algorithms and the software development.

Organization. A typical day during the two weeks course consists of two general lectures by the principal speakers in the morning, each one-and-a-half hours in duration. There will be a more specialized one hour topical lecture after lunch. The speakers will vary and we will occasionally have introductions to topic related software packages. In the later afternoon there will be a loosely organized two hour brain-storming session.

Necessary background. The main requirements are mathematical maturity and an open mind toward connecting mathematics to the world around it in new ways. No specialized knowledge in the two application areas will be assumed. Some background in algorithmic thinking and using computers will be helpful. We recommend the following texts for background reading.

Carl Brandon John Tooze. Introduction to Protein Structure. Garland, 1991.

Mark de Berg, Otfried Schwarzkopf, Marc van Kreveld, and Mark Overmars. Computational Geometry. Algorithms and Applications. Springer-Verlag, 1997.

Herbert Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge Univ. Press, 2001.

Yukio Matsumoto. An Introduction to Morse Theory. AMS, 2002.

James Munkres. Elements of Algebraic Topology. Addison Wesley, 1984.

Robert Tarjan. Data Structures and Network Algorithms. SIAM, 1983.

Tree


Local arrangements
. The participants of the short course and the instructors will be housed at one of the University of Minnesota's dormitories. Meals will be served at the the dormitory dining facility. Each participant will be provided with shared office space including an individual computer workstation. Lectures and problem-solving sessions will use the IMA's classroom, multimedia, and computer facilities. There are expected to be visits to relevant laboratories on the University of Minnesota campus.

Application and selection procedure. The IMA New Directions Short Courses will be limited to 25 participants. All successful applicants will be funded for travel and local expenses. Please see the IMA reimbursement policy for details about airfare. Applicants are required to submit a curriculum vita and a statement about their interest in the course, its place in their future research plans, and its expected impact on their research and teaching. A committee consisting of the course instructors and IMA directors will select the participants from among the applicants.

Short Course Schedule and Talk Materials

WEEK 1
TUESDAY, JULY 6
All lectures will be held in 409 Lind Hall
TIME
     LECTURE
8:30
Introduction
10:30
Delaunay Triangulation  Slides:   pdf
1:00
Alpha Shapes   Slides:   pdf
2:30
SOFTWARE DEMOS AND DISCUSSIONS
3:45
4:00
Reception
WEDNESDAY, JULY 7
All lectures will be held in 409 Lind Hall
TIME
     LECTURE
8:30
Wrap   Slides:   pdf
10:30
Surface Reconstraction with Crust   Slides:   pdf
1:30
Approximating Point-Cloud Datasets with Simplicial Complexes
Slides:   pdf
3:00
SOFTWARE DEMOS AND DISCUSSIONS
THURSDAY, JULY 8
All lectures will be held in 409 Lind Hall
TIME
LECTURE
8:30
Incremental Computation of Betti Numbers and Union-Find
Slides:   pdf
10:30
Persistence  Slides:   pdf
1:30
Persistence and Spectral Sequences
3:00
SOFTWARE DEMOS AND DISCUSSIONS: 3D-printing
Guest Lecturer: Brad Fox, General Pattern
FRIDAY, JULY 9
All lectures will be held in 409 Lind Hall
TIME
     LECTURE
8:30
Delaunay Triangulation Algorithm (Part I)   Slides:   pdf
10:30
Randomized Analysis (Part I)   Slides:   pdf
3:00
SOFTWARE AND DISCUSSIONS: CGAL
Guest Lecturer: Menelaos Karavelas
WEEK 2
MONDAY, JULY 12
All lectures will be held in 409 Lind Hall
TIME
LECTURE
8:30
Morse-Theory 2-dimensional PL Case   Slides:   pdf
10:30
Jacobi Sets and Correspondences   Slides:   pdf
1:30
Session: Setting Up the Participant Projects
3:00
Rachael Brady
Duke University

Demonstration: Morse Complex and Correspondence Software

3D Morse Complex Visualization Tool - note: the GAMMA colormap is best
Morse3DViewer.zip

TUESDAY, JULY 13
All lectures will be held in 409 Lind Hall
TIME
     LECTURE
8:30
Introduction to Protein Structure   Slides:   pdf
10:30
Interface Surfaces   Slides:     pdf
1:30
3:00
BRAIN STORMING
WEDNESDAY, JULY 14
All lectures will be held in 409 Lind Hall
TIME
     LECTURE
8:30 Dominique Attali
Polytechnical University of Grenoble

Medial Axes

Slides:   pdf

10:30
Elevation Function
1:30
Students work on their projects
3:00
BRAIN STORMING
6:00 Workshop Dinner Kafe 421 in Dinkytown
421 14th Ave SE.
Minneapolis
Phone: (612) 623-4900
THURSDAY, JULY 15
All lectures will be held in 409 Lind Hall
TIME
LECTURE
8:30
Marching Cubes
Rest of the Time: Working on Projects
FRIDAY, JULY 16
All lectures will be held in 409 Lind Hall
TIME
     LECTURE
8:30
Damrong Guoy
University of Illinois - Urbana-Champaign
Henry King
University of Maryland
Kevin Knudson
Mississippi State University
Neza Mramor
University of Ljubljana

Discrete v. Computational Morse Theory

Paper:   pdf

David Snyder
Texas State University
Joh-Joef Leth
Aalborg University
Todd Moeller
Georgia Institute of Technology
Avrahim Goldstein
City University of New York

Persistence of Jacobi Sets

Report:   pdf

1:30
wrap up I
3:00
wrap up II


LIST OF CONFIRMED PARTICIPANTS

Name Department Affiliation
Stephen Ahearn Dept. of Mathematics and Computer Science Macalester College
Douglas N. Arnold Institute for Mathematics and its Applications University of Minnesota
Dominique Attali Lab. des Images & des Signaux Polytechnical University of Grenoble
Rachael Brady Computer Science Duke University
Peter Cholak Department of Mathematics University of Notre Dame
Isabel Darcy   University of Iowa
Herbert Edelsbrunner Computer Science Department Duke University
Paul Andrew Fabel   Mississippi State University
Brad Fox   General Pattern Company
Avraham Goldstein   City University of New York
Damrong Guoy   University of Illinois - Urbana-Champaign
John L. Harer Department of Mathematics Duke University
Diane Hoffoss Department of Mathematics and Computer Science University of San Diego
Menelaos Karavelas Computer Science & Engineering Department Notre Dame University
Henry C. King   University of Maryland
Kevin Knudson Department of Mathematics and Statistics Mississippi State University
Wojciech Komornicki Department of Mathematics Hamline University
Nikolai Krylov School of Engineering & Science International University Bremen
John-Josef Leth Department of Mathematical Sciences Aalborg University
Debra Lewis IMA University of Minnesota
Paul McCreary Department of Mathematics Xavier University of Louisiana
Mike Melko Department of Mathematics Northern State University
Yuriy Mileyko Department of Mathematical Sciences New Jersey Institute of Technology
Todd Moeller Department of Mathematics Georgia Institute of Technology
Robert F. Morse Dept. of Electrical Engineering and Computer Science University of Evansville
Neza Mramor Computer and Information Science University of Ljubljana
Junalyn Navarra-Madsen Molecular and Cell Biology Dept. University of Texas - Dallas
Valerie Peterson Department of Mathematics University of Illinois - Urbana-Champaign
Victor Reiner Department of Mathematics University of Minnesota
William Rundell   National Science Foundation
David Rusin Department of Mathematical Sciences Northern Illinois University
Peter Saveliev Department of Mathematics Marshall University
Arnd Scheel Institute for Mathematics and its Applications University of Minnesota
David Snyder Department of Mathematics Texas State University
Christopher Stark Division of Mathematical Sciences National Science Foundation
Hongyuan Zha Department of CSE Pennsylvania State University
Ludmil Zikatanov   Pennsylvania State University

Photo Gallery

IMA New Directions Program