UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Optimization Problems in Computational Topology

PDE and Applied Math Seminar

Speaker: Anil N. Hirani, University of Illinois at Urbana-Champaign
Location: 1147 MSB
Start time: Tue, May 29 2012, 3:10PM

Computational topology is a relatively new field for quantifying topological information in images, meshes, and other types of data. I will describe several related optimization problems which extend the reach of computational topology in new directions. One problem is the computation of harmonic forms. The computation of harmonic 1-forms on surfaces has been addressed by a number of researchers in computer graphics with applications to texture mapping and vector field design. More generally, harmonic forms are a crucial ingredient for solving vector eliiptic PDEs. I will describe two methods based on finite element exterior calculus. One of these is based on eigenvector computation and the other is based on a discrete version of the Hodge-deRham theorem: the differential form in a cohomology class which has the smallest L2-norm is harmonic. This problem is thus L2 minimization subject to a cohomology constraint using rational values. Another class of problems is one in which the minimization is in L1 norm, the constraint is homological, and the values are integers. I will describe the solution of a previously open problem of finding the least spanning area surface of a knot in polynomial time when the knot is embedded in certain special spaces like the ordinary 3-space or 3-sphere. This may be useful as a preliminary combinatorial step for minimal surface computations.