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)dATeam 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