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-3aTeam 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