The Cake-Cutting Algorithm in Motion

Animated GIF89 image of the cake-cutting algorithm.

The animation shows the sequence of counties allocated to Congressional districts by the cake-cutting algorithm. In this implementation of the algorithm, the cake-cutting knife blade is deemed to have passed over a county when it reaches the center of the county. At each step, the next county added to the district is the westernmost county contiguous to any county already in the district. Ties are broken by an alphabetical ordering of the counties. A district is considered complete when adding a county to it would increase rather than decrease the district's departure from ideal size. (For example, if a district's current population is 500,000 and the ideal size is 550,000, a county will be added only if its population is less than 100,000.)

The bar graph at right records the growth of population in the 12 districts as counties are allocated to them.

The animation revealed a flaw in the algorithm I noticed only belatedly, after the print edition of American Scientist had gone to press. The last county added to the last district (colored bright red) is not the easternmost county in the state, as one would expect it to be. The reason is that the last county added is not contiguous to the others in the district. It is included in the final district only because the program has nowhere else to put it.