Minimum Cuts, Maximum Area, and Duality

Gilbert Strang
Massachusetts Institute of Technology

The oldest competition for an optimal shape (area-maximizing) was won by the circle. We propose a proof that uses the support function of the set -- a dual description that linearizes the isoperimetric problem.

Then we measure the perimeter in different ways, which changes the problem (and has applications in medical imaging). 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 discusses the **max flow-min cut theorem** for continuous flows. Usually this applies to discrete flows on graphs. The maximum flow out of a region equals the capacity of the minimum cut. This duality connects to the constrained isoperimetric problems that produce minimum cuts, and to the Cheeger constant. A key is that extreme points in BV norms are 0-1 functions -- in the discrete case this is because incidence matrices of graphs are totally unimodular, and we look for the analogous property for differential operators.

Presentation (PDF File)

Back to Graph Cuts and Related Discrete or Continuous Optimization Problems