2007美国大学生数学建模竞赛A题特等奖论文

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

Team1034 Page5of21

toapply.However,theydonotconsideranyotherpossiblyimportantconsiderationsfordistricts,suchas:geographicfreauresofthestateorhowwelltheyencompasscities.

1.2 DevelopingOurApproach

Sinceourgoalistocreatenewmethodsthataddtothediversityofmodelsavailabletoacommittee,weshouldfocusoncreatingdistrictboundariesindependentlyofcurrentdivisions.Notonlyhasthisapproachnotbeenexploredtoitsfullest,butitisnotobviouswhycountiesareagoodbeginningpointforamodel:Countiesarecreatedinthesame arbitrarywayasdistricts,sotheymightalsocontainbiases,sincecountiesaretypically notmuchsmallerthandistricts.Manyofthedivisiondependentmodelsenduprelaxingtheirboundariesfromcountylinesinordertomaintainequalpopulations,whichmakestheinitialassumption ofusing countydivisionsuseless,andalso allows forgerrymanderingifthisrelaxationmethodisnotwellregulated.

Treatingthestateascontinuous(i.e. withoutpreexistingdivisions)doesnotleadto

anyspecifictypeofapproach.Itgivesusalotoffreedom,butatthesametimewecanimposemoreconditions.IftheForrestandHaleet.al.methodsareanyindication,weshouldfocusonkeepingcitieswithindistrictsandintroducegeographicalconsiderations.(Notethattheseconditionsdonothavetobeconsideredifweweretotreattheproblemdiscretelybecausecurrentdivisions,likecounties,areprobablydependentonprominentgeographicalfeatures.)

Goal:Createamethodforredistrictingastatebytreatingthestatecontinu- ously.Werequirethefinaldistrictstocontainequalpopulationsandbecontiguous.Additionally,thedistrictsshouldbeassimpleaspossible(see §2foradefinitionofsimple)andoptimallytakeintoaccountimportant geographicalfeaturesofthestate.

2 NotationandDefinitions

? contiguous:AsetRiscontiguousifitispathwise-connected.

? compactness:Wewouldlikethedefinitionofcompactnesstobeintuitive. One waytolookatcompactnessistheratiooftheareaofaboundedregiontothesquareofitsperimeter. Inotherwords

AR 1 CR= p = Q R2 4πwhereCR isthecompactnessofregionR,AR isthearea,pR istheperimeterand

Qistheisoperimetricquotient. Wedonotexplicitelyusethisequation,butwedo keepthisideainmindwhenweevaluateourmodel.

? simple:Simpleregionsarecompactandconvex.Notethatthisdescribesarelativequality,sowecancompareregionsbytheirsimplicity.

本文来源：https://www.bwwdw.com/article/4qqd.html