Voronoi Tesselation: ask students to apply this algorithm to avoid future gov't shutdowns

Political polarization is caused in part by Congressional districts gerrymandered to be homogeneous enough to preserve party seats.  Our representatives don't have to please a mix reflecting the whole country, or even their local region, but only of a set of like-minded constituents.  What if we mandated (well, suggested or promoted) that after the next decennial Census, districts were created from a Voronoi tesselation of each state.  I've had this thought for years, but the current debacle in Washington brings it to mind again.  Here's a Voronoi diagram from http://upload.wikimedia.org/wikipedia/commons/thumb/2/20/Coloured_Voronoi_2D.svg/500px-Coloured_Voronoi_2D.svg.png.   You get the idea just from looking at it: "The partitioning of a plane with  points into convex polygons such that each polygon contains exactly one generating point and every point in a given polygon is closer to its generating point than to any other" (http://mathworld.wolfram.com/VoronoiDiagram.html).  Can your students apply the Voronoi algorithm to tesselate their state?  

Like most of my great ideas, this one's already been thought of (at home I'm known as Dr. Nobel Price - of Sesame Street fame).  See this article (summary lifted below) describing such a redistricting of New York: http://rangevoting.org/Week.8.lukas.svec.pdf.  And see the "pretty pictures" of Texas, Virginia and New Jersey here (this article's got a bit of political slant, or at least an anti-redistricting committee slant):Theoretical Issues in Political Districting, by Brian Olson & Warren D. Smith. Third PRELIMINARY draft August 2011 (http://rangevoting.org/TheorDistrict.html#PrettyPic).  They compare the Voronoi approach to redistricting with 2 others.  Here is a Voronoi diagram of Texas they display, from http://rangevoting.org/SpannGulottaKaneMCM2007.pdf:

 

These ideas tie political science, mathematics, algorithms and computational complexity.  Voronoi algorithms are used in image processing and many other computational areas.  I'm not a teacher, so I can't suggest how to turn this into a lesson, but if I were back in high school, I'd love to have had this presented to me!

Kathleen

 

 

 

Summary of the article mentioned above:

Applying Voronoi Diagrams to the Redistricting Problem

Lukas Svec, Sam Burden, Aaron Dilley, University of Washington, Seattle, WA, Advisor: James Allen Morrow

Gerrymandering is an issue plaguing legislative redistricting. We present a novel approach to redistricting that uses Voronoi and population-weighted Voronoiesquediagrams. Voronoi regions are contiguous, compact, and simple to generate. Regions drawn with Voronoiesque diagrams attain small population variance and relative geometric simplicity. As a concrete example, we apply 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 generates districts with an average population of (3.34±0.74)%. We discuss possible refinements that might result in smaller population variation while maintaining the simplicity of the regions and objectivity of the method.

Promote content

Featured content: 

Not Featured