Applying Voronoi Diagrams to the Redistricting Problem Mav10.2007 Abstract Gerrymandering is an issue plaguing legislative redistricting resulting from inade- uate regulation. Here, we present a novel approach to the redistricting problem, an approach that uses a state's population distribution to draw the legislative bound aries. Our method utilizes Voronoi and population-weighted Voronoiesque diagrams and was chosen for the simplicity of the generated partition: Voronoi regions are con- tiguous, compact, and simple to generate. We found regions drawn with voronoiesque diagrams attained small population variance and relative geometric simplicity. As a concrete example, we applied our methods to partition New York state. Since New York must be divided into 29 legislative districts, each receives roughly 3.44 of the population. Our Voronoiesque diagram method generated 29 regions with an average population of (3.34+0.74)%. We discuss several refinements that could be made to the methods presented which may result in smaller population variation between re gions while maintaining the simplicity of the regions and objectivity of the method Finally, we provide a short statement that could be issued to the voters of New York state to explain our method and justify its fairness to them
Applying Voronoi Diagrams to the Redistricting Problem May 10, 2007 Abstract Gerrymandering is an issue plaguing legislative redistricting resulting from inadequate regulation. Here, we present a novel approach to the redistricting problem, an approach that uses a state’s population distribution to draw the legislative boundaries. Our method utilizes Voronoi and population-weighted Voronoiesque diagrams, and was chosen for the simplicity of the generated partition: Voronoi regions are contiguous, compact, and simple to generate. We found regions drawn with Voronoiesque diagrams attained small population variance and relative geometric simplicity. As a concrete example, we applied our methods to partition New York state. Since New York must be divided into 29 legislative districts, each receives roughly 3.44 % of the population. Our Voronoiesque diagram method generated 29 regions with an average population of (3.34 ± 0.74)%. We discuss several refinements that could be made to the methods presented which may result in smaller population variation between regions while maintaining the simplicity of the regions and objectivity of the method. Finally, we provide a short statement that could be issued to the voters of New York state to explain our method and justify its fairness to them. 1
Team 1034 Page 2 of 21 Contents 1 Introduction 1.1 Current Models 1.2 Developing Our Approach 2 Notation and definitions 3 Theoretical evaluation of our model 4 Method Description 4.1 Voronoi Diagrams 4.1.1 Useful Features of Voronoi diagrams 4.2 Voronoiesque Diagrams 7889 4.3 Determining Generator Points Using Population Density Distributions 4.4 Procedure for Creating Regions using Voronoi and Voronoiesque Diagrams. 10 5 Redistricting in New York State opulation Density Map 5.2 Limitations of the Image-Based Density Map 11 5.3 Selecting Generator Points 5.4 Applying Voronoi Diagrams to NY 14 5.5 Applying Voronoiesque Diagrams to NY 14 5.6 Precisely Defining Boundary line 6 Analysis 6.1 New York State result 6.2 General results 7 Improving the Method 7.1 Boundary Refinement 72G Obstacles 8 Bulletin to the voters of the state of New york 9 Conclusion List of figures 1 Illustration of Voronoi diagram generated with Euclidean metric. Note the ompactness and simplicity of the regions. 2 Illustration of the process of growing a Voronoiesque diagram with respect to a population density. Only three three generator points are used. Figures from left to right iterate with time
Team 1034 Page 2 of 21 Contents 1 Introduction 4 1.1 Current Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Developing Our Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Notation and Definitions 5 3 Theoretical Evaluation of our Model 6 4 Method Description 7 4.1 Voronoi Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.1.1 Useful Features of Voronoi Diagrams . . . . . . . . . . . . . . . . . . 8 4.2 Voronoiesque Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.3 Determining Generator Points Using Population Density Distributions . . . 9 4.4 Procedure for Creating Regions using Voronoi and Voronoiesque Diagrams . 10 5 Redistricting in New York State 10 5.1 Population Density Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.2 Limitations of the Image-Based Density Map . . . . . . . . . . . . . . . . . 11 5.3 Selecting Generator Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.4 Applying Voronoi Diagrams to NY . . . . . . . . . . . . . . . . . . . . . . . 14 5.5 Applying Voronoiesque Diagrams to NY . . . . . . . . . . . . . . . . . . . . 14 5.6 Precisely Defining Boundary Lines . . . . . . . . . . . . . . . . . . . . . . . 17 6 Analysis 17 6.1 New York State Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 6.2 General Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 7 Improving the Method 18 7.1 Boundary Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 7.2 Geographic Obstacles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 8 Bulletin to the Voters of the State of New York 19 9 Conclusion 20 List of Figures 1 Illustration of Voronoi diagram generated with Euclidean metric. Note the compactness and simplicity of the regions. . . . . . . . . . . . . . . . . . . . 7 2 Illustration of the process of ‘growing’ a Voronoiesque diagram with respect to a population density. Only three three generator points are used. Figures from left to right iterate with time. . . . . . . . . . . . . . . . . . . . . . . . 9
Team 1034 Page 3 of 21 3 Illustration of creating divisions by first subdividing the map. Left: Pop- ulation density distribution of hypothetical map with five desired districts Middle: A subdivision of the map into two regions generated from two un- shown generator points. Right: Final division of each subregion from the middle figure into desired final division 4 New York State population density map. Data obtained from a 792-by-660 pixel raster image; color and height indicate the relative population density at each point. 5 Depiction of the implamentation of Voronoi diagrams with the manhat tan metric in the three step process of: assigning degeneracies to generator points, using the degenerate points to generate regions using the Voronoi agram method, and creating subregions of the regions generated by de- generate points. Only the last two steps are depicted. The process for Voronoiesque diagrams is the same.(Dots in each region represent genera- tor point locations. 6 Voronoi diagrams generated with three distance metrics before subdivision f densely populated regions (Dots in each region represent generator point 7 Districts created by the Voronoiesque diagram for New York state AverageS locations.) population per region =(3.34+ 0.74)%.(Dots in each region represent generator Do int locations. 8 Illustration of Voronoi diagram generation which takes geographic obstacles into accoun
Team 1034 Page 3 of 21 3 Illustration of creating divisions by first subdividing the map. Left: Population density distribution of hypothetical map with five desired districts. Middle: A subdivision of the map into two regions generated from two unshown generator points. Right: Final division of each subregion from the middle figure into desired final divisions. . . . . . . . . . . . . . . . . . . . . 10 4 New York State population density map. Data obtained from a 792-by-660 pixel raster image; color and height indicate the relative population density at each point. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5 Depiction of the implamentation of Voronoi diagrams with the Manhattan metric in the three step process of: assigning degeneracies to generator points, using the degenerate points to generate regions using the Voronoi diagram method, and creating subregions of the regions generated by degenerate points. Only the last two steps are depicted. The process for Voronoiesque diagrams is the same. (Dots in each region represent generator point locations.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6 Voronoi diagrams generated with three distance metrics before subdivision of densely populated regions. (Dots in each region represent generator point locations.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 7 Districts created by the Voronoiesque diagram for New York state. Average population per region = (3.34 ± 0.74)%. (Dots in each region represent generator point locations.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 8 Illustration of Voronoi diagram generation which takes geographic obstacles into account. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Team 1034 Page 4 of 21 1 Introduction Defining Congressional districts has long been a source of controversy in the United States Since the district-drawers are chosen by those currently in power, the boundaries are often created to influence future elections by grouping an unfavorable minority demographic with a favorable majority; this process is called Gerrymandering. It is common for districts to take on bizarre shapes, spanning slim sections of multiple cities and criss-crossing the countryside in a haphazard fashion. The only lawful restrictions on legislative boundaries stipulate that districts must contain equal populations, but the makeup of the districts left entirely to the district-drawers. In the United Kingdom and Canada, the districts are more compact and intuitive. Their success in mitigating Gerrymandering is attributed to having turned over the task of boundary-drawing to nonpartisan advisory panels. However, these independent com- missions can take 2-3 years to finalize a new division plan, calling their effectiveness into question. It seems clear that the U.S. should establish similar unbiased commissions, yet make some effort to increase the efficiency of these groups. Accordingly, our goal is to develop a small toolbox that aids in the redistricting process. Specifically, we will create a model that draws legislative boundaries using simple geometric constructions 1.1 Current models The majority of methods for creating districts fall into two categories: ones that depend on a current division arrangement(most commonly counties) and ones that do not depend on current divisions. Most fall into the former category. By using current divisions the problem is reduced to grouping these divisions in a desirable way using a multitude of mathematical procedures. Mehrotra et al. uses graph partitioning theory to cluster counties to total population variation of around 2% of the average district size [8. Hess and Weaver use an iterative process to define population centroids, use integer programming to group counties into equally populated districts, and then reiterate the process until the centroids reach a limit 5. Garfinkel and Nemhauser use iterative matrix operations to search for district combinations that are contiguous and compact 3. Kaiser begins with the current districts and systematically swaps populations with adjacent districts [4 All of these methods use counties as their divisions since they partition the state into a relatively small number of sections. This is necessary because most of the mathematical tools they use become slow and imprecise with many divisions. (This is the same as saying they become unusable in the limit when the state is divided into more continuous sections.)Thus using small divisions, like zip codes which on average are 5 times smaller The other category of methods is less common. Out of all our researched papers d documentation, there were only two methods that did not depend on current state divisions. Forrest's method continually divides a state into halves while maintaining pop- ulation equality until the required number of districts is satisfied [4, 5. Hale, Ransom and Ramsey create pie-shaped wedges about population centers. This creates homogeneous districts which all contain portions of a large city, suburbs, and less populated areas [4 hese approaches are noted for being the least biased since their only consideration is population equality and do not use preexisting divisions. Also, they are straightforward
Team 1034 Page 4 of 21 1 Introduction Defining Congressional districts has long been a source of controversy in the United States. Since the district-drawers are chosen by those currently in power, the boundaries are often created to influence future elections by grouping an unfavorable minority demographic with a favorable majority; this process is called Gerrymandering. It is common for districts to take on bizarre shapes, spanning slim sections of multiple cities and criss-crossing the countryside in a haphazard fashion. The only lawful restrictions on legislative boundaries stipulate that districts must contain equal populations, but the makeup of the districts is left entirely to the district-drawers. In the United Kingdom and Canada, the districts are more compact and intuitive. Their success in mitigating Gerrymandering is attributed to having turned over the task of boundary-drawing to nonpartisan advisory panels. However, these independent commissions can take 2-3 years to finalize a new division plan, calling their effectiveness into question. It seems clear that the U.S. should establish similar unbiased commissions, yet make some effort to increase the efficiency of these groups. Accordingly, our goal is to develop a small toolbox that aids in the redistricting process. Specifically, we will create a model that draws legislative boundaries using simple geometric constructions. 1.1 Current Models The majority of methods for creating districts fall into two categories: ones that depend on a current division arrangement (most commonly counties) and ones that do not depend on current divisions. Most fall into the former category. By using current divisions, the problem is reduced to grouping these divisions in a desirable way using a multitude of mathematical procedures. Mehrotra et.al. uses graph partitioning theory to cluster counties to total population variation of around 2% of the average district size [8]. Hess and Weaver use an iterative process to define population centroids, use integer programming to group counties into equally populated districts, and then reiterate the process until the centroids reach a limit [5]. Garfinkel and Nemhauser use iterative matrix operations to search for district combinations that are contiguous and compact [3]. Kaiser begins with the current districts and systematically swaps populations with adjacent districts [4]. All of these methods use counties as their divisions since they partition the state into a relatively small number of sections. This is necessary because most of the mathematical tools they use become slow and imprecise with many divisions. (This is the same as saying they become unusable in the limit when the state is divided into more continuous sections.) Thus using small divisions, like zip codes which on average are 5 times smaller than a county in New York, becomes impractical. The other category of methods is less common. Out of all our researched papers and documentation, there were only two methods that did not depend on current state divisions. Forrest’s method continually divides a state into halves while maintaining population equality until the required number of districts is satisfied [4, 5]. Hale, Ransom and Ramsey create pie-shaped wedges about population centers. This creates homogeneous districts which all contain portions of a large city, suburbs, and less populated areas [4]. These approaches are noted for being the least biased since their only consideration is population equality and do not use preexisting divisions. Also, they are straightforward
Team 1034 Page 5 of 21 to apply. However, they do not consider any other possibly important considerations for districts, such as: geographic freaures of the state or how well they encompass citi 1.2 Developing Our Approach Since our goal is to create new methods that add to the diversity of models available to a committee, we should focus on creating district boundaries independently of current divisions. Not only has this approach not been explored to its fullest, but it is not obvious why counties are a good beginning point for a model: Counties are created in the same arbitrary way as districts, so they might also contain biases, since counties are typically not much smaller than districts. Many of the division dependent models end up relaxin their boundaries from county lines in order to maintain equal populations, which makes the initial assumption of using county divisions useless, and also allows for gerrymandering if this relaxation method is not well regulated Treating the state as continuous (i.e. without preexisting divisions) does not lead any specific type of approach. It gives us a lot of freedom, but at the same time we can impose more conditions. If the Forrest and Hale etal. methods are any indication, we should focus on keeping cities within districts and introduce geographical considerations. (Note that these conditions do not have to be considered if we were to treat the problem discretely because current divisions, like counties, are probably dependent on prominent geographical features. Goal: Create a method for redistricting a state by treating the state continu- ously. We require the final districts to contain equal populations and be contiguous. Additionally, the districts should be as simple as possible(see $2 for a definition of simple) and optimally take into account important geographical features of the state 2 Notation and definitions contiguous: A set R is contiguous if it is pathwise-connected compactness: We would like the definition of compactness to be intuitive. One way to look at compactness is the ratio of the area of a bounded region to the square of its perimeter. In other words C PR where Cr is the compactness of region R, AR is the area, PR is the perimeter and Q is the isoperimetric quotient. We do not explicitely use this equation, but we do keep this idea in mind when we evaluate our model. simple: Simple regions are compact and convex. Note that this describes a relative quality, so we can compare regions by their simplici
Team 1034 Page 5 of 21 to apply. However, they do not consider any other possibly important considerations for districts, such as: geographic freaures of the state or how well they encompass cities. 1.2 Developing Our Approach Since our goal is to create new methods that add to the diversity of models available to a committee, we should focus on creating district boundaries independently of current divisions. Not only has this approach not been explored to its fullest, but it is not obvious why counties are a good beginning point for a model: Counties are created in the same arbitrary way as districts, so they might also contain biases, since counties are typically not much smaller than districts. Many of the division dependent models end up relaxing their boundaries from county lines in order to maintain equal populations, which makes the initial assumption of using county divisions useless, and also allows for gerrymandering if this relaxation method is not well regulated. Treating the state as continuous (i.e. without preexisting divisions) does not lead to any specific type of approach. It gives us a lot of freedom, but at the same time we can impose more conditions. If the Forrest and Hale et.al. methods are any indication, we should focus on keeping cities within districts and introduce geographical considerations. (Note that these conditions do not have to be considered if we were to treat the problem discretely because current divisions, like counties, are probably dependent on prominent geographical features.) Goal: Create a method for redistricting a state by treating the state continuously. We require the final districts to contain equal populations and be contiguous. Additionally, the districts should be as simple as possible (see §2 for a definition of simple) and optimally take into account important geographical features of the state. 2 Notation and Definitions • contiguous: A set R is contiguous if it is pathwise-connected. • compactness: We would like the definition of compactness to be intuitive. One way to look at compactness is the ratio of the area of a bounded region to the square of its perimeter. In other words CR = AR p2 R = 1 4π Q where CR is the compactness of region R, AR is the area, pR is the perimeter and Q is the isoperimetric quotient. We do not explicitely use this equation, but we do keep this idea in mind when we evaluate our model. • simple: Simple regions are compact and convex. Note that this describes a relative quality, so we can compare regions by their simplicity