2004 IMA New Directions Short Course
Computational Topology
July 616, 2004
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/
From July 616, 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 oneandahalf
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 brainstorming 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. SpringerVerlag,
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.
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 problemsolving 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 

8:30 
Introduction 
10:30 
Delaunay Triangulation Slides:
pdf 
1:00 

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 

10:30 
Surface Reconstraction with Crust Slides:
pdf

1:30 
Approximating PointCloud 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 UnionFind
Slides: pdf 
10:30 

1:30 
Persistence and Spectral Sequences 
3:00 
SOFTWARE DEMOS AND DISCUSSIONS:
3Dprinting
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 

WEEK 2 
MONDAY, JULY 12
All lectures will be held in 409 Lind Hall 
TIME 
LECTURE 
8:30 
MorseTheory 2dimensional 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 
Splay trees and Amortization

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) 6234900 
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  UrbanaChampaign 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 JohJoef
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  UrbanaChampaign 
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 
JohnJosef 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 NavarraMadsen 
Molecular and Cell Biology Dept. 
University of Texas  Dallas 
Valerie Peterson 
Department of Mathematics 
University of Illinois  UrbanaChampaign 
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
