Minimum Cuts and Maximum Area
- Date: 04/03/2007
Gilbert Strang (Massachusetts Institute of Technology)
Simon Fraser University
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.
SFU CSC Distinguished Speaker Series 2007