2007a2007 a o p electoral redistricting with moment of inertia_W

1、1更多数学建模资料请关注微店店铺“数学建模学习交流”/RHO6PSpAElectoral Redistricting with Moment of Inertia and Diminishing Halves ModelsAndrew Spann, Dan Gulotta, Daniel Kane Presented July 9,20082Outline1. Introduction2. Motivation3. Simplifying Assumptions4. Moment of InertiaMethod5. Diminishing Halves

2、 Methods6. Quantitative Compactness Analysis7. Conclusion3Problem Statement: Congressional Apportionment We wish to draw congressional districts for astate. Goal: Algorithm that avoids Gerrymandering. Want to create “simplest” shapes. Definition of “simple” left to problem solvers. Only rule is that

3、 districts have equal population.4Gerrymandering ExamplesAdapted from National Atlas of the United States.5MotivationMany possible criteria suggested inliterature. Equality of districtsize Compactness Contiguity Similarity to existingborders Targeted homogeneity/heterogeneityInstead of specifying ma

4、ny properties, we wish to explicitly specify as fewas possible.Additional properties become an emergent behavior.6MotivationOur algorithms will use only the criteria of1. Equal population districts2. CompactnessExamine map afterwards to determine emergent properties.7Simplifying AssumptionsWe make t

5、he following simplifying assumptions in our model: A 2% error tolerance from the mean in size of district population is acceptable. Euclideangeometry:variations in longitudinal spacing negligible. County borders not sacred (ratio of counties:districts in many states necessitates cutting between bord

6、ers).8Extracting 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.9Test DataTX20,851,820327530NY18,976,457296398IL12,419,293198078AZ

7、5,130,63281934StatePopulationDistrictsNon-empty Census Tracts10Algorithms for Fair ApportionmentWe will now compare two methods for apportioning districts1. Moment of InertiaMethod2. Diminishing Halves Method (Recursive Splitting)11Moment of Inertia MethodIntuition:Minimize the expected squared dist

8、ance between all pairs of people in a district. Equivalent to physics concept of moment of inertia. One of the first methods to appear in literature (Hess 1965 ) Results in districts that are not only connected, but also convex, which limits the possibilities of oddly shaped districts12Moment of Ine

9、rtia Method Moment of Inertia given by PPi(Xi X )2.i Equals minY P Pi(Xi Y )2.i Define districts andcenters. Given centers optimize districts by computing “size”parameters. Given districts optimize centers as centers of mass. Gives iterative method to converge to near optimal solution.13Diminishing

10、Halves MethodsIntuition:Divide the state into two halves of equal population. Then divide those halves recursively. Suggested by Forrest1964. Many different ways to divide state inhalf. After experimentation, we choose thefollowing:1. Treat the population data as regression coordinates.2. Compute th

11、e best fit squared distance (bfsd) line to the data.3. Use a line with slope perpendicular to this bfsd line to divide thestate.14Diminishing Halves MethodsCompute best fit squared distance line based on orthogonal distance todata. Best fit line for given slope contains center of mass. Line of form

12、(X X) sin + (Y Y ) cos = 0. Line minimizes 2E(X X) sin + (Y Y ) cos =sin2 Var X + 2 sin cos Cov (X, Y ) + cos2 Var Y . 2Cov(X,Y ) Optimal angle satisfies tan(2) = VarXVarY .1516171819Quantitative Measures of Compactness Inverse Roeck Test. Let C be the smallest circle containingthe region, R.Measure

13、Area(C) .Area(R) Schwartzberg Test.ComputePerimeter .4Area Length-Width Test. Inscribe the region intherectangle with largest length-to-width ratio. CalculateLength of Rectangle .Width of RectangleSmallernumbers arebetter.Circles give optimal value 1. See Young 1988 for a review.20Compactness Result

14、sMoI = Moment of Inertia, DH = Diminishing Halves.Smaller numbers correspond to more compact districts.NY (MoI)NY (DH)2.29 0.662.50 0.871.64 0.621.74 0.691.91 0.611.91 0.77TX (MoI)TX (DH)2.04 0.642.76 1.661.14 0.091.27 0.201.72 0.572.30 1.73IL (MoI)IL (DH)1.90 0.362.49 0.991.28 0.261.35 0.241.55 0.392.01 0.96AZ (MoI)AZ (DH)2.18 0.562.69 0.911.17 0.081.29 0.151.77 0.512.07 0.79DistrictsInv. RoeckSchwartzbergLength-Width21Conclusion Obtain nice districts despite few specified criteria. Both methods give r