Doctoral Program in Computer Science
365 5th Avenue
New York City 10016
Room 4319
Phone: 212.817.8190
Fax: 212.817.1510
compsci@gc.cuny.edu
  Click here to go to the Graduate Center main page.

Computer Science Colloquium
 


Thursday, March 11, 4:15pm, room 9206/9207
change of venue 9206/9207 -> 4102 (Science Center)
 
Herbert Edelsbrunner  
(Duke University)
 
"A combinatorial algorithm based on Jacobi sets of multiple Morse functions"
 
Jacobi sets of multiple Morse functions have applications in Computer Graphics, Structural Biology (e.g., understanding protein interaction), Oceanography, and Celestial Mechanics. (For some discussion of this see biogeometry.cs.duke.edu/meetings/ITR/03jun/presentations/ungor.03jun.pdf and/or http://www.cs.duke.edu/~edels/TriTop/). As an example, imagine the gravitational potential of the planets in our solar system defining a smooth map on the three-dimensional space. The planets themselves form local maxima. An interesting saddle point lies between the Earth and the Moon where the gravitational pull cancels. The trajectory of this point can be modeled as a portion of the Jacobi curve of two smooth functions on space-time: the gravitational potential and time. More generally, the Jacobi set of two or more generic smooth functions on a manifold contains all points at which the matrix of partial derivatives has rank deficiency at least one. These notions will be described and illustrated.

Inspired by the smooth concept, we study an analogous notion for piecewise linear maps over a triangulated manifold and we describe a combinatorial algorithm based on a definition of critical points. As a particularly easy special case, this algorithm computes the contour (or silhouette) of a triangulated surface embedded in space.

 
The Colloquium is supported by generous contributions from the CUNY Faculty Development Program, Bloomberg, Information Builders, Inc. and qbt Systems, Inc.