* Faculty       * Staff       * Students & Alumni       * Committees       * Contact       * Institute Directory
* Undergraduate Program       * Graduate Program       * Courses       * Institute Catalog      
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Colloquia       * Seminars       * News       * Events       * Institute Events      
* Overview       * Lab Manual       * Institute Computing      
No Menu Selected

* News


A Discrete Global Minimization Algorithm for Continuous Variational Problems

Shlomo Gortler
Harvard University

Thursday, October 6, 2005
JEC 3117 - 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.


There are many applications where one needs to search for a "function" that has "minimal energy" while satisfying some boundary constraints. As a simple example, consider the problem of finding the minimal area soap bubble surface that spans a wireframe boundary. Numerical methods are typically only good at finding local minima to such variational problems.

In this talk, we show how global optima can be found as the limit of a set of purely combinatorial problems. These combinatorial problems can be thought of higher dimensional analogues of the "shortest path in planar graph" problem. For example, when the problem dimension is 3, the combinatorial problem is to find a "discrete minimal surface" in a volumetric cellular complex. We then show how these combinatorial problems can be solved in polynomial time by reducing them to instances of MIN-CUT.

We will then explore an application of these ideas to 3-camera stereo vision.


Steven (aka Shlomo) Gortler, is the Robert I. Goldman Professor of Computer Science at Harvard University. Shlomo's main area of research is computer graphics, specializing in rendering and geometry, but is often convinced to work on other things as well.

Hosted by: Daniel Freedman (x4785)

Last updated: September 30, 2005