《数学建模》美赛优秀论文：2007 A O P Electoral Redistricting with Moment of Inertia

Electoral Redistricting with moment of Inertia and Diminishing Halves Models Andrew Spann, Dan Gulotta, Daniel Kane Presented July 9, 2008

Electoral Redistricting with Moment of Inertia and Diminishing Halves Models Andrew Spann, Dan Gulotta, Daniel Kane Presented July 9, 2008 1

Outline 1. Introduction 2. Motivation 3. Simplifying Assumptions 4. Moment of Inertia Method 5. Diminishing Halves Methods 6. Quantitative Compactness Analysis 7. Conclusion

Outline 1. Introduction 2. Motivation 3. Simplifying Assumptions 4. Moment of Inertia Method 5. Diminishing Halves Methods 6. Quantitative Compactness Analysis 7. Conclusion 2

Problem Statement: Congressional Apportionment We wish to draw congressional districts for a state Goal: Algorithm that avoids gerrymandering · Want to create“ simplest” shapes. · Definition of“ simple” left to problem solvers. e Only rule is that districts have equal population

Problem Statement: Congressional Apportionment • We wish to draw congressional districts for a state. • Goal: Algorithm that avoids Gerrymandering. • Want to create “simplest” shapes. • Definition of “simple” left to problem solvers. • Only rule is that districts have equal population. 3

Gerrymandering Examples Mohme Canton Lake Havasu City Phot Illinois Arizona Adapted from National Atlas of the United States

Gerrymandering Examples Adapted from National Atlas of the United States. 4

Motivation Many possible criteria suggested in literature Equality of district size e Compactness · Contiguity Similarity to existing borders Targeted homogeneity/heterogeneity Instead of specifying many properties, we wish to explicitly specify as few as possible. Additional properties become an emergent behavior 5

Motivation Many possible criteria suggested in literature. • Equality of district size • Compactness • Contiguity • Similarity to existing borders • Targeted homogeneity/heterogeneity Instead of specifying many properties, we wish to explicitly specify as few as possible. Additional properties become an emergent behavior. 5

Motivation Our algorithms will use only the criteria of 1. Equal population districts 2. Compactness Examine map afterwards to determine emergent roperties

Motivation Our algorithms will use only the criteria of 1. Equal population districts 2. Compactness Examine map afterwards to determine emergent properties. 6

Simplifying assumptions We make the following simplifying assumptions in our model: o a 2 error tolerance from the mean in size of district population is acceptable Euclidean geometry: variations in longitudinal spacing negligible County borders not sacred (ratio of counties: districts in many states necessitates cutting between borders)

Simplifying Assumptions We make the following simplifying assumptions in our model: • A 2% error tolerance from the mean in size of district population is acceptable. • Euclidean geometry: variations in longitudinal spacing negligible. • County borders not sacred (ratio of counties:districts in many states necessitates cutting between borders). 7

Extracting test data Perl script extracts US Census data at the census tract level Discretizes problem into points with a latitude ongitude, and population For New York, 6398 tracts of nonzero population, median 2518 people

Extracting test data • Perl script extracts US Census data at the census tract level. • Discretizes problem into points with a latitude, longitude, and population. • For New York, 6398 tracts of nonzero population, median 2518 people. 8

Test Data State Population Districts Non-empty Census Tracts 20.851.820 32 7530 NY‖18,976,457 29 6398 12.419.293 19 8078 aZ 5,130,632 1934

Test Data State Population Districts Non-empty Census Tracts TX 20,851,820 32 7530 NY 18,976,457 29 6398 IL 12,419,293 19 8078 AZ 5,130,632 8 1934 9

Algorithms for Fair Apportionment e will now compare two methods for apportioning districts 1. Moment of inertia method 2. Diminishing Halves Method(Recursive Splitting 10

Algorithms for Fair Apportionment We will now compare two methods for apportioning districts 1. Moment of Inertia Method 2. Diminishing Halves Method (Recursive Splitting) 10