《数学建模》美赛优秀论文：2007 A O Applying Voronoi Diagrams to the Redistricting Problem

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 inade￾quate 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. 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: 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 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 Manhat￾tan 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 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.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 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 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 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]. 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 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 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

Team 1034 Page 6 of 21 Voronoi diagrams: a partition of the plane with respect to n nodes in the plane such that points in the plane are in the same region of a node if they are closer te that node than to any other point(for a detailed description, see 54.1) generator point: a node of a Voronoi diagram degeneracy: the number of districts represented by one generator point Voronoiesque diagram: a variation of the Voronoi diagram based on equal masses of the regions(see $4.2 population center: a region of high population density 3 Theoretical evaluation of our model How we analyze our model's results is a tricky affair since there is disagreement in the redistricting literature on key issues. Population equality is the most well defined. By law, the populations within districts have to be the same to within a few percent of the average population per district. No specific percentage is given, but be assumed to be Creating a successful redistricting model also requires contiguity. In accordance with tate law, districts need to be path-wise connected so that one part of a district cannot be on one side of the state and the other part on the other end of the state. This requirement is meant to maintain locality and community within districts. It does not, however, restrict islands districts from including islands if the island, s population is below the required population level Finally, there is a desire for the districts to be, in one word, simple. There is little no agreement on this characteristic, and the most common terminology for this is compact Taylor defines simple as a measure of divergence from compactness due to indentation of the boundary and gives an equation relating the non-reflexive and reflexive interior angles of a regions boundary 9. Young provides seven more measures of compactness. The Roeck test is a ratio of the area of the largest inscribable circle in a region to the area of that region. The Schwartzberg test takes ratio between the adjusted perimeter of a egion to a the perimeter of a circle whose area is the same as the area of the region. The moment of inertia test measures relative compactness by comparing"moments of inertia"of different district arrangements. The Boyce-Clark test compares the difference between points on a district's boundary and the center of mass of that district, where zero deviation of these differences is most desirable. The perimeter test compares different district arrangements buy computing the total perimeter of each. Finally, there is the visual test. This test decides simplicity based on intuition 11] Young notes that "a measure of compactness only indicates when a plan is more redistricting proposals, it is also difficult to compare the consensus on how to analyze compact than another"[11]. Thus, not only is there no inally, we remark that the above list only constrains the shape of generated districts We have not mentioned of any other potentially relevant feature. For instance, it does not consider how well populations are distributed or how well the new district boundaries conform with other boundaries, like counties or zip codes. Even with this short list, it is

Team 1034 Page 6 of 21 • Voronoi diagrams: a partition of the plane with respect to n nodes in the plane such that points in the plane are in the same region of a node if they are closer to that node than to any other point (for a detailed description, see §4.1) • generator point: a node of a Voronoi diagram • degeneracy: the number of districts represented by one generator point • Voronoiesque diagram: a variation of the Voronoi diagram based on equal masses of the regions (see §4.2) • population center: a region of high population density 3 Theoretical Evaluation of our Model How we analyze our model’s results is a tricky affair since there is disagreement in the redistricting literature on key issues. Population equality is the most well defined. By law, the populations within districts have to be the same to within a few percent of the average population per district. No specific percentage is given, but be assumed to be around 5%. Creating a successful redistricting model also requires contiguity. In accordance with state law, districts need to be path-wise connected so that one part of a district cannot be on one side of the state and the other part on the other end of the state. This requirement is meant to maintain locality and community within districts. It does not, however, restrict islands districts from including islands if the island’s population is below the required population level. Finally, there is a desire for the districts to be, in one word, simple. There is little to no agreement on this characteristic, and the most common terminology for this is compact. Taylor defines simple as a measure of divergence from compactness due to indentation of the boundary and gives an equation relating the non-reflexive and reflexive interior angles of a region’s boundary [9]. Young provides seven more measures of compactness. The Roeck test is a ratio of the area of the largest inscribable circle in a region to the area of that region. The Schwartzberg test takes ratio between the adjusted perimeter of a region to a the perimeter of a circle whose area is the same as the area of the region. The moment of inertia test measures relative compactness by comparing “moments of inertia” of different district arrangements. The Boyce-Clark test compares the difference between points on a district’s boundary and the center of mass of that district, where zero deviation of these differences is most desirable. The perimeter test compares different district arrangements buy computing the total perimeter of each. Finally, there is the visual test. This test decides simplicity based on intuition [11]. Young notes that “a measure [of compactness] only indicates when a plan is more compact than another”[11]. Thus, not only is there no consensus on how to analyze redistricting proposals, it is also difficult to compare them. Finally, we remark that the above list only constrains the shape of generated districts. We have not mentioned of any other potentially relevant feature. For instance, it does not consider how well populations are distributed or how well the new district boundaries conform with other boundaries, like counties or zip codes. Even with this short list, it is

Team 1034 Page 7 of 21 Voronoi Diagram Figure 1: Illustration of Voronoi diagram generated with Euclidean metric. Note the compactness and simplicity of the regions clear that we are not in a position to define a rigorous definition of simplicity. What we can do, however, is identify features of our proposed districts which are simple and which are not. This is in line with our goal defined in sec. 1. 2, since this list can be provided to a districting commission who decide how relevant those simple features are. We do not explicitly define simple, we loosely evaluate simplicity based on overall contiguity, compactness, convexity, and intuitiveness of the models districts. 4 Method Description Our approach depends heavily on using Voronoi diagrams. We begin with a definition, its features, and motivate its application to redistricting 4.1 Voronoi diagrams A Voronoi diagram is a set of polygons, called Voronoi polygons, formed with respect to n generator points contained in the Each generator pi is contained within a voronoi polygon V(pi) with the following property: v(pi)=iald(pi, q)sd(pj,q), if) where d(a, y) is the distance from point a to y That is, the set of all such q is the set of points closer to pi than to any other pj. Then the diagram is given by(see fig 1) V(p1),.,V(pn) Note that there is no assumption on the metric we use. Out of the many possible choices. we use the three most common: Euclidean Metric: d(p,q)=v(p-Ia)2+(p-3a

Team 1034 Page 7 of 21 Voronoi Diagram Figure 1: Illustration of Voronoi diagram generated with Euclidean metric. Note the compactness and simplicity of the regions. clear that we are not in a position to define a rigorous definition of simplicity. What we can do, however, is identify features of our proposed districts which are simple and which are not. This is in line with our goal defined in sec. 1.2, since this list can be provided to a districting commission who decide how relevant those simple features are. We do not explicitly define simple, we loosely evaluate simplicity based on overall contiguity, compactness, convexity, and intuitiveness of the model’s districts. 4 Method Description Our approach depends heavily on using Voronoi diagrams. We begin with a definition, its features, and motivate its application to redistricting. 4.1 Voronoi Diagrams A Voronoi diagram is a set of polygons, called Voronoi polygons, formed with respect to n generator points contained in the plane. Each generator pi is contained within a Voronoi polygon V (pi) with the following property: V (pi) = {q|d(pi, q) ≤ d(pj, q), i 6= j} where d(x, y) is the distance from point x to y That is, the set of all such q is the set of points closer to pi than to any other pj. Then the diagram is given by (see fig 1) V = {V (p1),...,V (pn)} Note that there is no assumption on the metric we use. Out of the many possible choices, we use the three most common: • Euclidean Metric: d(p, q) = q (xp − xq)2 + (yp − yq)2

Team 1034 Page 8 of 21 Manhattan Metric: d(p, q)=lTp-Iql+ lyp -yql Uniform Metric: d(p, q)=maxlIp-Iql, lyp-yal 4.1.1 Useful Features of Voronoi diagrams Here is a summary of relevant propert The Voronoi diagram for a given set of generator points is unique and produces polygons, which are path connected The nearest generator point to pi determines an edge of V(pi The polygonal lines of a Voronoi polygon do not intersect the generator points When working in the Euclidean metric, all regions are convex. These properties are important for our model. The first property tells us that less of how we choose our generator points we generate unique regions. This is good considering the politics of Gerrymandering. The second property implies that each is defined in terms of the surrounding generator points while in turn, each region is rel- atively compact. These features of Voronoi diagrams effectively satisfy two out of the three criteria for partitioning a region: contiguity and simplicity 4.2 Voronoiesque Diagrams The second method we use to create regions is a modification of the intuitive construction of Voronoi diagrams. The method does not fall under the definition of Voronoi diagrams but since it is similar to Voronoi diagrams, we call them Voronoiesque diagrams. One way to visualize the construction of Voronoi diagrams is to imagine shapes(determined by the metric) that grow radially outward at a constant rate from each generator point. In the Euclidean metric these shapes are circles. In the Manhattan metric they are diamonds In the Uniform metric, they are squares. The interior of these shapes form the regions of the diagram. As the regions intersect, they form the boundary lines for the regions. With this picture in mind, we define Voronoiesque diagrams to be the boundaries defined by the intersections of these growing shapes. The fundamental difference between Voronoi and Voronoiesque diagrams is that Voronoiesque diagrams grow the shapes radially outward at a constant rate like Voronoi diagrams. Their radial growth is defined with respect to some real function on a subset of R2(representing the space on which the diagram is being generated ) See fig 2 More rigorously, we define a Voronoi diagram to be the intersections of the v(e)'s, where is the Voronoiesque region iteration t. With every iterations f(,y)dA=/ f(a, y)dA

Team 1034 Page 8 of 21 • Manhattan Metric: d(p, q) = |xp − xq| + |yp − yq | • Uniform Metric: d(p, q) = max {|xp − xq|, |yp − yq |} 4.1.1 Useful Features of Voronoi Diagrams Here is a summary of relevant properties: • The Voronoi diagram for a given set of generator points is unique and produces polygons, which are path connected. • The nearest generator point to pi determines an edge of V (pi) • The polygonal lines of a Voronoi polygon do not intersect the generator points. • When working in the Euclidean metric, all regions are convex. These properties are important for our model. The first property tells us that regard￾less of how we choose our generator points we generate unique regions. This is good when considering the politics of Gerrymandering. The second property implies that each region is defined in terms of the surrounding generator points while in turn, each region is rel￾atively compact. These features of Voronoi diagrams effectively satisfy two out of the three criteria for partitioning a region: contiguity and simplicity. 4.2 Voronoiesque Diagrams The second method we use to create regions is a modification of the intuitive construction of Voronoi diagrams. The method does not fall under the definition of Voronoi diagrams, but since it is similar to Voronoi diagrams, we call them Voronoiesque diagrams. One way to visualize the construction of Voronoi diagrams is to imagine shapes (determined by the metric) that grow radially outward at a constant rate from each generator point. In the Euclidean metric these shapes are circles. In the Manhattan metric they are diamonds. In the Uniform metric, they are squares. The interior of these shapes form the regions of the diagram. As the regions intersect, they form the boundary lines for the regions. With this picture in mind, we define Voronoiesque diagrams to be the boundaries defined by the intersections of these growing shapes. The fundamental difference between Voronoi and Voronoiesque diagrams is that Voronoiesque diagrams grow the shapes radially outward at a constant rate like Voronoi diagrams. Their radial growth is defined with respect to some real function on a subset of R2 (representing the space on which the diagram is being generated). See fig.2 More rigorously, we define a Voronoi diagram to be the intersections of the V(t) i ’s, where V(t) i is the Voronoiesque region, or just ‘region’, generated by the generator point pi at iteration t. With every iterations, V(t) i ⊂ V(t+1) i and Z Vi f(x, y)dA = Z Vj f(x, y)dA

Team 1034 Page 9 of 21 Figure 2: Illustration of the process ofgrowing a Voronoiesque diagram with respect to a population density. Only three three generator points are used. Figures from left to right terate with time for all vi, vi representing different regions. The manner in which the v (t)'s are grown radially from one iteration to the next is determined by the metric used What's useful about Voronoiesque d agran is that their growth can De c ontrolled by requiring that the area under the function f for each region is the same at every iteration In our model, we take f to be the population distribution of the state. Thus the abov equation is a statement of population equality. Also, when f is constant, the regions grow at a constant rate, so the resulting diagram is voronoi. The final consideration for using Voronoiesque diagrams is determining the locat generator points 4.3 Determining Generator Points Using Population Density Dis- For now, we have defined how to generate regions given a set of generator points. Here we consider how to define the generator points in order to create Voronoi and Vornoiesque diagrams. In the case of Voronoi diagrams, this is our only degree of freedom since gen- erator points generate unique Voronoi regions. We found no well defined algorithm to do this, but instead came up with a procedure that functions decently Our first approach is to place generator points at the m largest set of peaks that are well distributed throughout the state, (where m is the required number of districts in that state). By choosing generator points in this way, we keep larger cities within the boundaries we will generate with Voronoi or Vornoiesque diagrams and we make sure the generator points are well dispersed throughout the state. One problem that arises is when cities are so large that in order for districts to hold the same amount of people, a city must be divided into districts. A perfect example is New York City, which contains enough people to hold 13 districts. Taking large cities into account takes extra consideration. Our second approach is to choose the largest peaks in the population distribution and assign each peak with a weight. The weight for each generator point is the number of districts the population surrounding that peak needs to be divided into. We call this weight the degeneracy of the generator point. We begin assigning generator points to the highest populated cities with their corresponding degeneracies until the sum of all the generator points and their respective degeneracies is equal to m. In other words, until

Team 1034 Page 9 of 21 Figure 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. for all Vi, Vj representing different regions. The manner in which the V(t) i ’s are grown radially from one iteration to the next is determined by the metric used. What’s useful about Voronoiesque diagrams is that their growth can be controlled by requiring that the area under the function f for each region is the same at every iteration. In our model, we take f to be the population distribution of the state. Thus the above equation is a statement of population equality. Also, when f is constant, the regions grow at a constant rate, so the resulting diagram is Voronoi. The final consideration for using Voronoiesque diagrams is determining the location for generator points. 4.3 Determining Generator Points Using Population Density Dis￾tributions For now, we have defined how to generate regions given a set of generator points. Here we consider how to define the generator points in order to create Voronoi and Vornoiesque diagrams. In the case of Voronoi diagrams, this is our only degree of freedom since gen￾erator points generate unique Voronoi regions. We found no well defined algorithm to do this, but instead came up with a procedure that functions decently. Our first approach is to place generator points at the m largest set of peaks that are well distributed throughout the state, (where m is the required number of districts in that state). By choosing generator points in this way, we keep larger cities within the boundaries we will generate with Voronoi or Vornoiesque diagrams and we make sure the generator points are well dispersed throughout the state. One problem that arises is when cities are so large that in order for districts to hold the same amount of people, a city must be divided into districts. A perfect example is New York City, which contains enough people to hold 13 districts. Taking large cities into account takes extra consideration. Our second approach is to choose the largest peaks in the population distribution and assign each peak with a weight. The weight for each generator point is the number of districts the population surrounding that peak needs to be divided into. We call this weight the degeneracy of the generator point. We begin assigning generator points to the highest populated cities with their corresponding degeneracies until the sum of all the generator points and their respective degeneracies is equal to m. In other words, until:

Team 1034 Page 10 of 21 Figure 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 degeneracy of generator pt. =m As we will see when we apply our model to New York, this method works well. It should be noted, though, that this is not the only way to define the location of generator points, but it is a very good start 4.4 Procedure for Creating Regions using Voronoi and Voronoiesque Diagrams Once we have our generator points, we can generate our diagrams with two more steps first generate the diagram using the given generator points. Within each generated region called a subdivision, with some degeneracy r, create r new generator points within that subdivision by finding the r largest population density peaks and create another diagram ee fig 3 5 Redistricting in New York State At this point, we have described a general procedure for generating political districts with Voronoi diagrams which seems effective. We now turn our attention to testing our models on New York has regions with large population density, has regions with constrained geography, and must be divided into many(29) regions

Team 1034 Page 10 of 21 Figure 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. X all generator pts. degeneracy of generator pt. = m As we will see when we apply our model to New York, this method works well. It should be noted, though, that this is not the only way to define the location of generator points, but it is a very good start. 4.4 Procedure for Creating Regions using Voronoi and Voronoiesque Diagrams Once we have our generator points, we can generate our diagrams with two more steps: first generate the diagram using the given generator points. Within each generated region, called a subdivision, with some degeneracy r, create r new generator points within that subdivision by finding the r largest population density peaks and create another diagram. See fig.3 5 Redistricting in New York State At this point, we have described a general procedure for generating political districts with Voronoi diagrams which seems effective. We now turn our attention to testing our models on New York. • has regions with large population density, • has regions with constrained geography, • and must be divided into many (29) regions