Minimum Cuts and Maximum Area

  • Date: 04/03/2007
Lecturer(s):

Gilbert Strang (Massachusetts Institute of Technology)

Location: 

Simon Fraser University

Topic: 

The oldest competition for an optimal shape (area-maximizing) was won by the circle. We want to give the thousandth proof !

Then we measure the perimeter in different ways, which changes the
problem (and has applications in medical imaging). If we use the line
integral of |dx| + |dy|, a square would win. Or if the boundary
integral of max(|dx|,|dy|) is given, a diamond has maximum area. When
the perimeter = integral of ||(dx,dy)|| around the boundary is given,
the area inside is maximized by a ball in the dual norm.

The second part describes the **max flow-min cut theorem** for
continuous flows. Usually it is for discrete flows on edges of graphs.
The maximum flow out of a region equals the capacity of the minimum
cut. This duality connects to the isoperimetric problems that produce
minimum cuts. But the flows are hard to find and a prize is unclaimed.

Other Information: 

SFU CSC Distinguished Speaker Series 2007

Sponsor: 

pimssfu