Minimum Cuts and Maximum Area
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.
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.
Speakers
Additional Information
SFU CSC Distinguished Speaker Series 2007
Gilbert Strang (Massachusetts Institute of Technology)
Gilbert Strang (Massachusetts Institute of Technology)