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