ApplyingVoronoiDiagramstotheRedistricting
Problem
May10,2007
Abstract
Gerrymanderingisanissueplaguing legislativeredistrictingresultingfrominade-quateregulation.Here,wepresentanovelapproachtotheredistrictingproblem,anapproachthatusesastate‘spopulationdistributiontodrawthelegislativebound-aries.OurmethodutilizesVoronoiandpopulation-weightedVoronoiesquediagrams, andwaschosenforthesimplicityofthegeneratedpartition:Voronoiregionsarecon-tiguous,compact,andsimpletogenerate.WefoundregionsdrawnwithVoronoiesquediagramsattainedsmallpopulationvarianceandrelativegeometricsimplicity.Asaconcreteexample,weappliedourmethodstopartitionNewYorkstate.SinceNewYorkmustbedivided into29legislativedistricts,each receivesroughly3.44 %ofthepopulation.OurVoronoiesquediagrammethod generated29regionswithanaveragepopulationof(3.34±0.74)%.Wediscussseveralrefinementsthatcouldbemadetothemethodspresentedwhichmayresultinsmallerpopulationvariationbetweenre-gionswhilemaintainingthesimplicityoftheregionsandobjectivityofthemethod.Finally,weprovideashortstatementthatcouldbeissuedtothevotersofNewYorkstatetoexplainourmethodandjustifyitsfairnesstothem.
1
Team1034 Page2of21
Contents
1 Introduction 4 1.1 CurrentModels ............................................................................................................... 4 1.2 DevelopingOurApproach .............................................................................................. 5 2 NotationandDefinitions 3 TheoreticalEvaluationofourModel 5 6
4 MethodDescription 7 4.1 VoronoiDiagrams ........................................................................................................... 7
4.1.1 UsefulFeaturesofVoronoiDiagrams .................................................................. 8 4.2 VoronoiesqueDiagrams ................................................................................................. 8 4.3 DeterminingGeneratorPointsUsingPopulationDensityDistributions... 9 4.4 ProcedureforCreatingRegionsusingVoronoiandVoronoiesqueDiagrams. 10 5 RedistrictinginNewYorkState 10 5.1 PopulationDensityMap.......................................................................................... 11 5.2 LimitationsoftheImage-BasedDensityMap ................................................................ 11 5.3 SelectingGeneratorPoints ............................................................................................ 11 5.4 ApplyingVoronoiDiagramstoNY ................................................................................ 14 5.5 ApplyingVoronoiesqueDiagramstoNY ...................................................................... 14 5.6 PreciselyDefiningBoundaryLines ............................................................................... 17 6 Analysis 17 6.1 NewYorkStateResults .................................................................................................. 17 6.2 GeneralResults ............................................................................................................. 18 7 ImprovingtheMethod 18 7.1 BoundaryRefinement ................................................................................................... 18 7.2 GeographicObstacles ................................................................................................... 19 8 BulletintotheVotersoftheStateofNewYork 9 Conclusion 19 20
ListofFigures
1 2
IllustrationofVoronoidiagramgeneratedwithEuclideanmetric.Notethecompactnessandsimplicityoftheregions. .............................................................................................. 7 Illustrationoftheprocessof?growing‘aVoronoiesquediagramwithrespecttoapopulationdensity.Onlythreethreegeneratorpointsareused.Figures
fromlefttorightiteratewithtime. ............................................................................... 9
Team1034 Page3of21
3
4
5
6
7 8
Illustrationofcreatingdivisionsbyfirstsubdividingthemap. Left: Pop-ulationdensitydistributionofhypotheticalmapwithfivedesireddistricts.Middle:Asubdivisionofthemapintotworegionsgeneratedfromtwoun-showngeneratorpoints. Right: Finaldivisionofeachsubregionfromthemiddlefigureintodesiredfinaldivisions. ........ 10 NewYorkStatepopulationdensitymap.Dataobtainedfroma792-by-660pixelrasterimage;colorandheightindicatetherelativepopulationdensity
ateachpoint ............................................................................................................. 12 DepictionoftheimplamentationofVoronoidiagramswiththeManhat- tanmetricinthethreestepprocessof:assigningdegeneraciestogeneratorpoints,usingthedegeneratepointstogenerateregionsusingtheVoronoidiagrammethod,andcreatingsubregionsoftheregionsgeneratedbyde-generatepoints.Onlythelasttwostepsaredepicted.TheprocessforVoronoiesquediagramsisthesame. (Dotsineachregionrepresentgenera-
torpointlocations.) ........................................................................................................ 13 Voronoidiagramsgeneratedwiththreedistancemetricsbeforesubdivisionofdenselypopulatedregions.(Dotsineachregionrepresentgeneratorpoint
locations.) ..................................................................................................................... 15 DistrictscreatedbytheVoronoiesquediagramforNewYorkstate.Averagepopulationperregion=(3.34±0.74)%. (Dotsineachregionrepresent generatorpointlocations.) ............................................................................................. 16 IllustrationofVoronoidiagramgenerationwhichtakesgeographicobstacles
intoaccount ................................................................................................................... 19
Team1034 Page4of21
1 Introduction
DefiningCongressionaldistrictshaslongbeenasourceofcontroversyintheUnitedStates.Sincethedistrict-drawersarechosenbythosecurrentlyinpower,theboundariesareoftencreatedtoinfluencefutureelectionsbygroupinganunfavorableminoritydemographicwithafavorablemajority;thisprocessiscalledGerrymandering.Itiscommonfordistrictstotakeonbizarreshapes,spanningslimsectionsofmultiplecitiesandcriss-crossingthecountrysideinahaphazardfashion.Theonlylawfulrestrictionsonlegislativeboundariesstipulatethatdistrictsmustcontainequalpopulations,butthemakeupofthedistrictsisleftentirelytothedistrict-drawers.
IntheUnitedKingdomandCanada,thedistrictsaremore compact andintuitive.TheirsuccessinmitigatingGerrymanderingisattributedtohavingturnedoverthetaskofboundary-drawingtononpartisanadvisorypanels.However,theseindependentcom-missionscantake2-3yearstofinalizeanewdivisionplan,callingtheireffectivenessintoquestion.ItseemsclearthattheU.S.shouldestablishsimilarunbiasedcommissions,yetmakesomeefforttoincreasetheefficiencyofthesegroups.Accordingly,ourgoalistodevelopasmalltoolboxthataidsintheredistrictingprocess. Specifically,wewillcreateamodelthatdrawslegislativeboundariesusingsimplegeometricconstructions.
1.1 CurrentModels
Themajorityofmethodsforcreatingdistrictsfallintotwocategories:onesthatdependon acurrentdivisionarrangement(mostcommonlycounties)andonesthatdonotdependoncurrentdivisions. Most fallintothe formercategory. By usingcurrent divisions,theproblemisreducedtogroupingthesedivisionsinadesirablewayusingamultitudeofmathematicalprocedures.Mehrotraet.al.usesgraphpartitioningtheorytoclustercountiestototalpopulationvariationofaround2%oftheaveragedistrictsize[8].HessandWeaveruseaniterativeprocesstodefinepopulationcentroids,useintegerprogrammingtogroupcountiesintoequallypopulateddistricts,and then reiterate the process untilthecentroidsreachalimit[5].GarfinkelandNemhauseruseiterativematrixoperationstosearchfordistrictcombinationsthatarecontiguousandcompact[3].Kaiserbeginswiththecurrentdistrictsandsystematicallyswapspopulationswithadjacentdistricts[4].Allofthesemethodsusecountiesastheirdivisionssincetheypartitionthestateintoarelativelysmallnumberofsections.Thisisnecessarybecausemostofthemathematicaltoolstheyusebecomeslowandimprecisewithmanydivisions.(Thisisthesameassayingtheybecomeunusableinthelimitwhenthestateisdividedintomorecontinuous sections.)Thususingsmalldivisions,likezipcodeswhichonaverageare5timessmaller thanacountyinNewYork,becomesimpractical.
Theothercategoryofmethodsislesscommon.Outofallourresearchedpapersanddocumentation,therewereonlytwomethodsthatdidnotdependoncurrentstatedivisions.Forrest‘smethodcontinuallydividesastateintohalveswhilemaintainingpop-ulationequalityuntiltherequirednumberofdistrictsissatisfied[4,5].Hale,RansomandRamseycreatepie-shapedwedgesaboutpopulationcenters.Thiscreateshomogeneousdistrictswhichallcontain portionsofalargecity,suburbs,andlesspopulatedareas[4].Theseapproachesarenotedforbeingtheleastbiasedsincetheironlyconsiderationispopulationequalityanddonotusepreexistingdivisions.Also,theyarestraightforward
相关推荐：
loading