2007ao將voronoi圖應(yīng)用于重新劃分問(wèn)題

更多學(xué)習(xí)資料，請(qǐng)關(guān)注淘寶店鋪：學(xué)神資料 ApplyingVoronoiDiagramstotheRedistrictingMay10,Gerrymanderingisanissueplaguinglegislativeredistrictingresultingfrominade-quateregulation.Here,wepresentanovelapproachtotheredistrictingproblem,anapproachthatusesastate’spopulationdistributiontodrawthelegislativebound-aries.OurmethodutilizesVoronoiandpopulation-weightedVoronoiesquediagrams,andwaschosenforthesimplicityofthegeneratedpartition:Voronoiregionsarecon-tiguous,compact,andsimpletogenerate.WefoundregionsdrawnwithVoronoiesquediagramsattainedsmallpopulationvarianceandrelativegeometricsimplicity.Asaconcreteexample,weappliedourmethodstopartitionNewYorkstate.SinceNewYorkmustbedividedinto29legislativedistricts,eachreceivesroughly3.44%ofthepopulation.OurVoronoiesquediagrammethodgenerated29regionswithanaveragepopulationof(3.34±0.74)%.Wediscussseveralrefinementsthatcouldbemadetothemethodspresentedwhichmayresultinsmallerpopulationvariationbetweenre-gionswhilemaintainingthesimplicityoftheregionsandobjectivityofthemethod.Finally,weprovideashortstatementthatcouldbeissuedtothevotersofNewYorkstatetoexplainourmethodandjustifyitsfairnesstothem.1 Notationand TheoreticalEvaluationofour Method RedistrictinginNewYork Improvingthe BulletintotheVotersoftheStateofNew ListofIllustrationofVoronoidiagramgeneratedwithEuclideanmetric.Notethecompactnessandsimplicityoftheregions Illustrationofcreatingdivisionsbyfirstsubdividingthemap.Left:Pop-ulationdensitydistributionofhypotheticalmapwithfivedesireddistricts.Middle:Asubdivisionofthemapintotworegionsgeneratedfromtwoun-showngeneratorpoints.Right:Finaldivisionofeachsubregionfromthemiddlefigureintodesiredfinal ateach DepictionoftheimplamentationofVoronoidiagramswiththeManhat-points,usingthedegeneratepointstogenerateregionsusingtheVoronoidiagrammethod,andcreatingsubregionsoftheregionsgeneratedbyde-generatepoints.Onlythelasttwostepsaredepicted.Theprocessfortorpoint DistrictscreatedbytheVoronoiesquediagramforNewYorkstate.Averagepopulationperregion=(3.34±0.74)%.(Dotsineachregionrepresentgeneratorpointlocations.) IllustrationofVoronoidiagramgenerationwhichtakesgeographicinto afavorablemajority;thisprocessiscalledGerrymandering.Itiscommonfordistrictstotakeonbizarreshapes,spanningslimsectionsofmultiplecitiesandcriss-crossingtheleftentirelytothedistrict-drawers.IntheUnitedKingdomandCanada,thedistrictsaremorecompactandintuitive.ofboundary-drawingtononpartisanadvisorypanels.However,theseindependentcom-makesomeefforttoincreasetheefficiencyofthesegroups.Accordingly,ourgoalistodevelopasmalltoolboxthataidsintheredistrictingprocess.Specifically,wewillcreateamodelthatdrawslegislativeboundariesusingsimplegeometricconstructions.acurrentdivisionarrangement(mostcommonlycounties)andonesthatdonotdependoncurrentdivisions.Mostfallintotheformercategory.Byusingcurrentdivisions,theproblemisreducedtogroupingthesedivisionsinadesirablewayusingamultitudeofmathematicalprocedures.Mehrotraet.al.usesgraphpartitioningtheorytoclustertogroupcountiesintoequallypopulateddistricts,andthenreiteratetheprocessuntiltosearchfordistrictcombinationsthatarecontiguousandcompact[3].KaiserbeginsAllofthesemethodsusecountiesastheirdivisionssincetheypartitionthestateintoarelativelysmallnumberofsections.Thisisnecessarybecausemostofthemathematicaltoolstheyusebecomeslowandimprecisewithmanydivisions.(ThisisthesameasthanacountyinNewYork,becomesimpractical.Theothercategoryofmethodsislesscommon.Outofallourresearchedpapersanddocumentation,therewereonlytwomethodsthatdidnotdependoncurrentstateRamseycreatepie-shapedwedgesaboutpopulationcenters.Thiscreateshomogeneousdistrictswhichallcontainportionsofalargecity,suburbs,andlesspopulatedareas[4].Theseapproachesarenotedforbeingtheleastbiasedsincetheironlyconsiderationispopulationequalityanddonotusepreexistingdivisions.Also,theyarestraightforwardtoapply.However,theydonotconsideranyotherpossiblyimportantconsiderationsfordistricts,suchas:geographicfreauresofthestateorhowwelltheyencompasscities.Sinceourgoalistocreatenewmethodsthataddtothediversityofmodelsavailabletoacommittee,weshouldfocusoncreatingdistrictboundariesindependentlyofcurrentwhycountiesareagoodbeginningpointforamodel:Countiesarecreatedinthesamearbitrarywayasdistricts,sotheymightalsocontainbiases,sincecountiesaretypicallynotmuchsmallerthandistricts.Manyofthedivisiondependentmodelsenduprelaxingtheirboundariesfromcountylinesinordertomaintainequalpopulations,whichmakesifthisrelaxationmethodisnotwellregulated.Treatingthestateascontinuous(i.e.withoutpreexistingdivisions)doesnotleadtoanyspecifictypeofapproach.Itgivesusalotoffreedom,butatthesametimewecanimposemoreconditions.IftheForrestandHaleet.al.methodsareanyindication,we(Notethattheseconditionsdonothavetobeconsideredifweweretotreattheproblemgeographicalfeatures.)Goal:Createamethodforredistrictingastatebytreatingthestatecontinu-ously.Werequirethefinaldistrictstocontainequalpopulationsandbe§2foradefinitionofsimple)andoptimallytakeintoaccountimportantgeographicalfeaturesofthestate.Notationandcontiguous:AsetRiscontiguousifitispathwise-compactness:Wewouldlikethedefinitionofcompactnesstobeintuitive.Oneofitsperimeter.InotherwordspCR pR

=1whereCRisthecompactnessofregionR,ARisthearea,pRistheperimeterandQistheisoperimetricquotient.Wedonotexplicitelyusethisequation,butwedokeepthisideainmindwhenweevaluateourmodel.quality,sowecancompareregionsbytheirsimplicity.Voronoidiagrams:apartitionoftheplanewithrespecttonnodesintheplanesuchthatpointsintheplaneareinthesameregionofanodeiftheyareclosertothatnodethantoanyotherpoint(foradetaileddescription,see§4.1)generatorpoint:anodeofaVoronoidegeneracy:thenumberofdistrictsrepresentedbyonegeneratorVoronoiesquediagram:avariationoftheVoronoidiagrambasedonequalmassesoftheregions(see§4.2)populationcenter:aregionofhighpopulationHowweanalyzeourmodel’sresultsisatrickyaffairsincethereisdisagreementintheredistrictingliteratureonkeyissues.Populationequalityisthemostwelldefined.Bylaw,thepopulationswithindistrictshavetobethesametowithinafewpercentoftheaveragepopulationperdistrict.Nospecificpercentageisgiven,butbeassumedtobearound5%.islandsdistrictsfromincludingislandsiftheisland’spopulationisbelowtherequiredpopulationlevel.Finally,thereisadesireforthedistrictstobe,inoneword,simple.Thereislittletoofaregion’sboundary[9].Youngprovidessevenmoremeasuresofcompactness.TheRoecktestisaratiooftheareaofthelargestinscribablecircleinaregiontotheareaofthatregion.TheSchwartzbergtesttakesratiobetweentheadjustedperimeterofaregiontoatheperimeterofacirclewhoseareaisthesameastheareaoftheregion.Themomentofinertiatestmeasuresrelativecompactnessbycomparing“momentsofbetweenpointsonadistrict’sboundaryandthecenterofmassofthatdistrict,wheredistrictarrangementsbuycomputingthetotalperimeterofeach.Finally,thereisthevisualtest.Thistestdecidessimplicitybasedonintuition[11].Youngnotesthat“ameasure[ofcompactness]onlyindicateswhenaplanismorecompactthananother”[11].Thus,notonlyistherenoconsensusonhowtoanalyzeredistrictingproposals,itisalsodifficulttocomparethem.Wehavenotmentionedofanyotherpotentiallyrelevantfeature.Forinstance,itdoesconformwithotherboundaries,likecountiesorzipcodes.Evenwiththisshortlist,itisVoronoiFigure1:IllustrationofVoronoidiagramgeneratedwithEuclideanmetric.Notethecompactnessandsimplicityoftheregions.clearthatwearenotinapositiontodefinearigorousdefinitionofsimplicity.Whatwearenot.Thisisinlinewithourgoaldefinedinsec.1.2,sincethislistcanbeprovidedtoadistrictingcommissionwhodecidehowrelevantthosesimplefeaturesare.Wedonotexplicitlydefinesimple,welooselyevaluatesimplicitybasedonoverallcontiguity,compactness,convexity,andintuitivenessofthemodel’sdistricts.Methodfeatures,andmotivateitsapplicationtoredistricting.generatorpointscontainedintheplane.EachgeneratorpiiscontainedwithinaVoronoipolygonV(pi)withthefollowingproperty:V(pi)={q|d(pi,q)≤d(pj,q),i=j}whered(x,y)isthedistancefrompointxtoThatis,thesetofallsuchqisthesetofpointsclosertopithantoanyotherpj.Thenthediagramisgivenby(seefig1)V={V(p1),...,VNotethatthereisnoassumptiononthemetricweuse.Outofthemanypossiblechoices,weusethethreemostcommon:EuclideanMetric:d(p,q)=(xp?xq)2+(yp?ManhattanMetric:d(p,q)=|xp?xq|+|yp?yqUniformMetric:d(p,q)=max{|xp?xq|,|yp?yqUsefulFeaturesofVoronoiTheVoronoidiagramforagivensetofgeneratorpointsisuniqueandproducespolygons,whicharepathconnected.Thesepropertiesareimportantforourmodel.Thefirstpropertytellsusthatregard-isdefinedintermsofthesurroundinggeneratorpointswhileinturn,eachregionisrel-ativelycompact.ThesefeaturesofVoronoidiagramseffectivelysatisfytwooutofthethreecriteriaforpartitioningaregion:contiguityandsimplicity.VoronoiesqueofVoronoidiagrams.ThemethoddoesnotfallunderthedefinitionofVoronoidiagrams,metric)thatgrowradiallyoutwardataconstantratefromeachgeneratorpoint.IntheEuclideanmetrictheseshapesarecircles.IntheManhattanmetrictheyarediamonds.IntheUniformmetric,theyaresquares.TheinterioroftheseshapesformtheregionsofataconstantratelikeVoronoidiagrams.Theirradialgrowthisdefinedwithrespecttogenerated).Seefig.2iV(t)istheVoronoiesqueregion,orjust‘region’,generatedbythegeneratorpointpiatiterationt.Witheveryiterations,i

V(t)?f(x,y)dA

f(x,iteratewithtime.iforallVi,Vjrepresentingdifferentregions.ThemannerinwhichtheV(t)’sareiWhat’susefulaboutVoronoiesquediagramsisthattheirgrowthcanbecontrolledbyInourmodel,wetakeftobethepopulationdistributionofthestate.Thustheaboveataconstantrate,sotheresultingdiagramisVoronoi.ThefinalconsiderationforusingVoronoiesquediagramsisdeterminingthelocationforgeneratorpoints.Fornow,wehavedefinedhowtogenerateregionsgivenasetofgeneratorpoints.Herediagrams.InthecaseofVoronoidiagrams,thisisouronlydegreeoffreedomsincegen-this,butinsteadcameupwithaprocedurethatfunctionsdecently.Ourfirstapproachistoplacegeneratorpointsatthemlargestsetofpeaksthatarewelldistributedthroughoutthestate,(wheremistherequirednumberofdistrictsinthatstate).Bychoosinggeneratorpointsinthisway,wekeeplargercitieswithintheboundarieswewillgeneratewithVoronoiorVornoiesquediagramsandwemakesurethegeneratorpointsarewelldispersedthroughoutthestate.Oneproblemthatarisesispeopletohold13districts.Takinglargecitiesintoaccounttakesextraconsideration.assigneachpeakwithaweight.Theweightforeachgeneratorpointisthenumberofdistrictsthepopulationsurroundingthatpeakneedstobedividedinto.Wecallthishighestpopulatedcitieswiththeircorrespondingdegeneraciesuntilthesumofallthegeneratorpointsandtheirrespectivedegeneraciesisequaltom.Inotherwords,until:ofthemapintotworegionsgeneratedfromtwounshowngeneratorpoints.Right:Finaldivisionofeachsubregionfromthemiddlefigureintodesiredfinaldivisions.allgenerator

degeneracyofgeneratorpt.=AswewillseewhenweapplyourmodeltoNewYork,thismethodworkswell.Itshouldbenoted,though,thatthisisnottheonlywaytodefinethelocationofgeneratorpoints,butitisaverygoodstart.ProcedureforCreatingRegionsusingVoronoiandVoronoiesqueOncewehaveourgeneratorpoints,wecangenerateourdiagramswithtwomoresteps:calledasubdivision,withsomedegeneracyr,creaternewgeneratorpointswithinthatSeefig.3RedistrictinginNewYorkonNewYork.andmustbedividedintomany(29)sincethesepointswilluniquelydetermineaVoronoidiagramforthestate.ThenwetocreateactualpoliticaldistrictsforNewYorkstate.ToapplyourVoronoidiagrammethodstoNewYork,wefirstobtainanapproximatepopulationdensitymapofthestate.TheU.S.CensusBureaumaintainsadatabase[2]whichcontainscensustract-levelpopulationstatistics;whencombinedwithboundarythan8,000peopleperregion[7].Unfortunately,ourlimitedexperiencewiththeCensusBureau’sdataformatpreventedusfromaccessingthisdatadirectly,andwecontentedourselveswitha792-by-660pixelapproximationtothepopulationdensitymap[6].representedpopulationdensityateachpoint.Toremoveartifactsintroducedbyusingacoarselatticerepresentationforfinely-distributeddata,weapplieda6-pixelmovingaveragefiltertothedensitymap.Theresultingpopulationdensityisshowninfig.4.milefromthefollowingset(measuredinpeoplepersquaremile):{0,10,25,50,100,250,500,1000,2500,5000}Thisprovidesadecentapproximationforregionswithadensitysmallerthan5,000theapproximationwillbreakdownatlargepopulationcenters.equalpopulations.NewYorkstatemustbedividedinto29congressionaldistrictstosupportitsshareofrepresentatives,soeachregionmustcontain≈3.45%ofthestate’spopulation.Sinceastate’spopulationisconcentratedprimarilyinasmallnumberofcities,weuselocalmaximaofthepopulationdensitymapascandidatesforgeneratorIfweweretosimplychoosethehighest29peaksfromthepopulationdensitymapasoursetofgeneratorpoints,theresultingsetwouldbecontainedentirelyinthelargestpopulationcentersandwouldnotbewelldistributedevenlyoverstate.ForthelargestprocessoffindinggeneratorpointsforthatregionandgenerateaVoronoidiagramfromthem.Seefig.3foranillustrationofthedecompositionbeforeandaftersubdivision.TopView:WhiteareasrepresenthighpopulationdensityoverNewYorkAngledView:ClearerviewofpopulationdistibutionoverNewrasterimage;colorandheightindicatetherelativepopulationdensityateachpoint.RegionscreatedusingtheManhattanmetricbeforesubdivisionsareim-mented.SubdivisionsarecreatedinNewYorkCity,Buffalo,Rochester,andoftheregionsgeneratedbydegeneratepoints.Onlythelasttwostepsaredepicted.Thepointlocations.)BasedonourdensitydataforNewYorkstate,wesubdividetheregionaroundNewCityreceives14districts,Buffalogets3,andRochesterandAlbanybothgetroughly2.Here,NewYorkCity’spopulationisunderestimatedsincetheaveragedensitytherefarexceedsourdata’sdensityrange.Withamoredetaileddataset,ourmethodwouldhavecalledforthecorrectnumberofsubdivisions.Thesimplestmethodweconsiderforgeneratingcongressionaldistrictsistosimplygen-eratethediscreteVoronoidiagramfromasetofgeneratorpoints.Weachievethisbyiteratively‘growing’regionsoutwardwiththefunctionfconstant.Thatwaytheregionsgrowataconstantrate,andhencetheresultingdiagramisvoronoi.Aregion’sgrowthislimitedateachstepbyitsradiusinacertainmetric;weconsideredtheEuclidean,samemethod.Unrefineddecompositionscanbeseeninfig.6.hattanmetrichassimplerboundariesandyieldsaslightlysmallerpopulationvariancebetweenregions.However,theVoronoiregionsaresosimplethatweprefertoaugmentthismethodwithpopulationweightsratherthanabandonitentirely.Fig.7showstheresultofthisdecomposition,alongwithexplodedviewsofthetworegionswhichweresubdividedmorethantwiceintherefinementstageofthediagramgeneration.Thepopulationcontainedineachregionissummarizedintable1.RegionRegionRegion123456789 ricbeforesubdivisions.Average=(3.5±

RegionscreatedusingtheEuclideanmet-ricbeforesubdivisions.Average=(3.7±RegionscreatedusingtheUnifrommet-ricbeforesubdivisions.AveragePopulation=(3.7±Figure6:Voronoidiagramsgeneratedwiththreedistancemetricsbeforesubdivisionofdenselypopulatedregions.(Dotsineachregionrepresentgeneratorpointlocations.)OverallNewYorkVoronoiesqueExplodedviewofregionsaround (c)ExplodedviewofregionsaroundLongFigure7:DistrictscreatedbytheVoronoiesquediagramforNewYorkstate.Averagepopulationperregion=(3.34±0.74)%.(DotsineachregionrepresentgeneratorpointItisnotsatisfactorytosaytheregionscreatedbyourmodelsshoulddefinethefinalboundarylocations.Intheleast,boundariesshouldbetweakedsothattheydon’tacci-dentalydividehousesintotwodistricts.However,giventhescaleatwhichtheVoronoicityblockspersquaremileinManhattan,whiletheminimumsizeofoneofourVoronoibypreexistingboundaries.NewYorkStateWeturnnowtoadiscussionofhowwellourresultsfromtheprevioussectionmeetouroriginalspecificationforredistricting.Intermsofsimplicityofgenerateddistricts,ourmetric:thegeneratedregionsarecontiguousandcompactwhiletheirboundaries,beingunionsoflinesegments,areaboutthesimplestthatcouldbeexpected.However,thisvarianceintheaveragepopulationperregionisontheorderoftheaveragepopulationAsmaybeexpectedinanysortofhigh-dimensionaloptimizationproblem,thereistheirrespectivepopulations.Accordingly,whenwemodifytheVoronoidiagrammethodafactoroffour—from±2.8%to±0.7%—whilesufferingasmalllossinthesimplicityoftheresultingregions.Inparticular,regionsintheVoronoiesquediagramsappeartobelesscompactandtheirboundariesaremorecomplicatedthantheirVoronoidiagramcounterparts,thoughcontiguityisstillmaintained.generatedfromeitherofourmethodswouldhavetomakesmall,localizedmodificationstoensurethedistrictboundariesmakesensefromapracticalperspective.Thoughthisourmethodswereaimingtoavoidinthefirstplace,wethinkthesizeofthenecessaryorVoronoiesqueregion(ontheorderoftensorhundredsofmiles)tomaketheneteffectofthesevariationsinsignificant.Therefore,thoughwehaveprovidedonlyafirst-ordertooccur.ingeneral?Weexaminetheresultsforanarbitrarystateincludingworstcasescenariosforeachcriteria.PopulationTypically,ourVoronoimethodhasthemostroomforerrorhere.Ifastatehasaseriesregions.However,ourfinalmethodfocusesprimarilyonpopulationsoequalityismucheasiertoregulatehere.Contiguityproblemsariseoftenifthestateitselfhaslittlecompactness,likeFlorida,orifthestatehassomesortofsoundlikeWashington.Thefirsttwomethodsfocusmoreit’spossibleforoneregiontobeseparatedbysomegeographicobstructionlikeabodyofwateroramountainrange.Againthefinalmethodfixesthisbygrowinginincrements,specifiedobstacles.Unfortunately,thefinalmethoddoesn’tdoeverything,itistheleastlikelycandidateforgeneratingcompactregions.Thefirsttwoaremostsuccessfulinthisarea.Thefirstissimilarinshapeandsizetothefirst.Furthermore,onenicepropertyofthegeneratedregionsfromthefirstmethodisthatthereisawaytomakeslightadjustmentstotheImprovingthetheseproblems.ConsidertheVoronoidiagrammethod.Weknowthisapproachisgoodatgeneratingpolygonaldistrictsbutnotassuccessfulatmaintainingpopulationequality.Onesuchafinitenumberoflinesegmentsthatpartiallydefinetheboundariesoftheseadjacentconvexity.Withthiswecanredrawboundariesbetweenregionsthataresignificantlydifferentinpopulationsizeandindoingsohelpequalizeeachoftheregions.attheregionwiththelowestpopulation,systematicallyincreasetheareaofthelow-otherprominentfeatures.TheVoronoiesquemethod,however,hasthepotentialtoim-regionscandetectadefinedgeographicboundaryandstopgrowinginthatdirection.Anillustrationofthisideaisshowninfig.8.Thesegeographicobstacleswouldbechosenbytheredistrictingcommittee.BulletintotheVotersoftheStateofNewREADONFORIMPORTANTINFORMATIONREGARDINGYOURREP-RESENTATIVEGOVERNMENTAuthoritieswithinyourstate’sgovernmentrecentlyrealizedthatduringrepresentationforallcitizens,theStateofNewYorkcommissionedaninterdisciplinaryteamofmathematiciansandengineerstocreateanobjectiveprocedureforredistrictingbecontainequalbeascompactaspossible,notunnecessarilysubdividelargeAccordingly,theycreatedasimplemethodforgeneratingdistrictsthatmeetthesecriteria.ThemethodisbasedonageometricalstructureknownasaVoronoidiagram,whichdescribesapartitionofyourstateintocompact,connectedregionsgeneratedfromasetofinitialpoints;seefigure1foranexample.Sincetheregionsaresupposedtoenvelopequalpopulati