haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

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

发布时间:2013-10-17 08:01:42  

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‘aVoronoiesquediagramwithrespecttoa

populationdensity.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

CRp = Q R2 4π

whereCR isthecompactnessofregionR,AR isthearea,pR istheperimeterand

Qistheisoperimetricquotient. Wedonotexplicitelyusethisequation,butwedo

keepthisideainmindwhenweevaluateourmodel.

? simple:Simpleregionsarecompactandconvex.Notethatthisdescribesarelativequality,sowecancompareregionsbytheirsimplicity.

Team1034 Page6of21

? Voronoidiagrams:apartitionoftheplanewithrespecttonnodesintheplane

suchthatpointsintheplaneareinthesameregionofanodeiftheyareclosertothatnodethantoanyotherpoint(foradetaileddescription,see§4.1)

? generatorpoint:anodeofaVoronoidiagram

? degeneracy: thenumberofdistrictsrepresented byonegeneratorpoint

? Voronoiesquediagram: avariationoftheVoronoidiagrambasedonequalmassesoftheregions(see§4.2)

? populationcenter:aregionofhighpopulationdensity

3 TheoreticalEvaluationofourModel

Howweanalyzeourmodel‘sresultsisatrickyaffairsincethereisdisagreementintheredistrictingliteratureonkeyissues.Populationequalityisthemostwelldefined.Bylaw,thepopulationswithindistrictshavetobethesametowithinafewpercentoftheaveragepopulationperdistrict.Nospecificpercentageisgiven,butbeassumedtobearound5%.

Creatingasuccessfulredistrictingmodelalsorequirescontiguity.Inaccordancewithstatelaw,districtsneed tobepath-wiseconnectedsothat onepartofadistrict cannotbeononesideofthestateandtheotherpartontheotherendofthestate.Thisrequirementismeant tomaintainlocalityandcommunitywithindistricts.Itdoesnot,however,restrict islandsdistrictsfromincludingislandsiftheisland‘spopulationisbelowtherequiredpopulationlevel.

Finally,thereisadesireforthedistrictstobe,inoneword,simple.Thereislittletonoagreementonthischaracteristic,andthemostcommonterminologyforthisiscompact.Taylordefinessimpleasameasureofdivergencefromcompactnessduetoindentationoftheboundaryandgivesanequationrelatingthenon-

reflexiveandreflexiveinterioranglesofaregion‘sboundary[9].Youngprovidessevenmoremeasuresofcompactness.TheRoecktestisaratiooftheareaofthelargestinscribablecircleinaregiontotheareaofthatregion.TheSchwartzbergtesttakesratiobetweentheadjustedperimeterofaregiontoatheperimeterofacirclewhoseareaisthesameastheareaoftheregion.Themomentofinertiatestmeasuresrelativecompactnessbycomparing―momentsofinertia‖ofdifferentdistrictarrangements.TheBoyce-

Clarktestcomparesthedifferencebetweenpointsonadistrict‘sboundaryandthecenterofmassofthatdistrict,wherezerodeviationofthesedifferencesismostdesirable.Theperimetertestcomparesdifferentdistrictarrangementsbuycomputingthetotalperimeterofeach.Finally,thereisthevisualtest.Thistestdecidessimplicitybasedonintuition[11].

Youngnotesthat―ameasure[ofcompactness]onlyindicateswhenaplanismore

compactthananother‖[11].Thus,notonlyistherenoconsensusonhowtoanalyzeredistrictingproposals,itisalsodifficulttocomparethem.

Finally,weremarkthattheabovelistonlyconstrainstheshapeofgenerateddistricts.Wehavenotmentionedofanyotherpotentiallyrelevantfeature.Forinstance,itdoesnotconsiderhowwellpopulationsaredistributedorhowwellthenewdistrictboundariesconformwithotherboundaries,likecountiesorzipcodes.Evenwiththisshortlist,itis

Team1034 Page7of21

VoronoiDiagram

Figure1:IllustrationofVoronoidiagramgeneratedwithEuclidean

metric.Notethecompactnessandsimplicityoftheregions.

clearthatwearenotinapositiontodefinearigorousdefinitionofsimplicity.Whatwecando,however,isidentifyfeaturesofourproposeddistrictswhicharesimpleandwhich

arenot.Thisisinlinewithourgoaldefinedinsec.1.2,sincethislistcanbeprovidedtoadistrictingcommissionwhodecidehowrelevantthosesimplefeaturesare.Wedonotexplicitlydefinesimple,welooselyevaluatesimplicitybasedonoverallcontiguity, compactness, convexity, and intuitiveness of the model’s districts.

4 MethodDescription

OurapproachdependsheavilyonusingVoronoidiagrams.Webeginwithadefinition,itsfeatures,andmotivateitsapplicationtoredistricting.

4.1 VoronoiDiagrams

AVoronoidiagramisasetof

polygons,calledVoronoipolygons,formedwithrespecttongeneratorpointscontainedintheplane.EachgeneratorpiiscontainedwithinaVoronoipolygonV(pi)withthefollowingproperty: V(pi)={q|d(pi,q)≤d(pj,q),iI=j}whered(x,y)isthedistancefrompointxtoy

Thatis,thesetofallsuchqisthesetofpointsclosertopithantoanyotherpj.Thenthediagramisgivenby(seefig1)

V={V(p1),...,V(pn)}

Notethatthereisnoassumptiononthemetricweuse.

Outofthemanypossiblechoices,weusethethreemostcommon:

? EuclideanMetric: d(p,q)= (xp?xq)2+(yp?yq)2

Team1034 Page8of21

? ManhattanMetric:d(p,q)=|xp?xq|+|yp?yq| ? UniformMetric:d(p,q)=max{|xp?xq|,|yp?yq|}

4.1.1 UsefulFeaturesofVoronoiDiagrams

Hereisasummaryofrelevantproperties:

? TheVoronoidiagramforagivenset ofgeneratorpointsisuniqueandproducespolygons,whicharepathconnected.

? Thenearestgeneratorpointtopi determinesanedgeofV(pi)

? ThepolygonallinesofaVoronoipolygondonotintersectthegeneratorpoints.

? WhenworkingintheEuclideanmetric,allregionsareconvex.

Thesepropertiesareimportantforourmodel.Thefirstpropertytellsusthatregard-

lessofhowwechooseourgeneratorpointswegenerateuniqueregions.ThisisgoodwhenconsideringthepoliticsofGerrymandering.

Thesecondpropertyimpliesthateachregionisdefinedintermsofthesurroundinggeneratorpointswhileinturn,eachregionisrel-

ativelycompact.ThesefeaturesofVoronoidiagramseffectivelysatisfytwooutofthethreecriteriaforpartitioningaregion: contiguityandsimplicity.

4.2 Voronoiesque Diagrams

ThesecondmethodweusetocreateregionsisamodificationoftheintuitiveconstructionofVoronoidiagrams.ThemethoddoesnotfallunderthedefinitionofVoronoidiagrams,butsinceitissimilartoVoronoidiagrams,wecallthemVoronoiesquediagrams.Oneway

tovisualizetheconstructionofVoronoidiagramsistoimagineshapes(determinedbythemetric)thatgrowradiallyoutwardataconstantratefromeachgeneratorpoint.IntheEuclideanmetrictheseshapesarecircles.IntheManhattanmetrictheyarediamonds.IntheUniformmetric,theyaresquares.Theinterioroftheseshapesformtheregionsofthediagram.Astheregionsintersect,theyformtheboundarylinesfortheregions.Withthispictureinmind,wedefineVoronoiesquediagramstobetheboundariesdefinedbytheintersectionsofthesegrowingshapes.ThefundamentaldifferencebetweenVoronoiandVoronoiesquediagramsisthatVoronoiesquediagramsgrowtheshapesradiallyoutwardataconstantratelikeVoronoidiagrams.TheirradialgrowthisdefinedwithrespecttosomerealfunctiononasubsetofR2(representingthespaceonwhichthediagramis beinggenerated).Seefig.2 Morerigorously,wedefineaVoronoidiagramtobetheintersectionsoftheV‘s,wherei (t) Vi istheVoronoiesqueregion,orjust?region‘,generatedbythegeneratorpointpiat iterationt.Witheveryiterations, (t)

and Vi

r (t) ?Vi (t+1) r

f(x,y)dA=

Vj f(x,y)dA Vi

Team1034 Page9of21

Figure2:Illustrationoftheprocessof?growing‘aVoronoiesquediagramwithrespecttoapopulationdensity.Onlythreethreegeneratorpointsareused.Figuresfromlefttorightiteratewithtime.

forallVi,Vjrepresentingdifferentregions.ThemannerinwhichtheV‘saregrownradiallyfromoneiti erationtothenextisdeterminedbythemetricused.

What‘susefulaboutVoronoiesquediagramsisthattheirgrowthcanbecontrolledbyrequiringthat the areaunder the functionfforeach regionisthe sameat every iteration.Inourmodel,wetakeftobethepopulationdistributionofthestate.Thustheaboveequationisastatementofpopulationequality.Also,whenfisconstant,theregionsgrowata constantrate,sotheresultingdiagram isVoronoi.

ThefinalconsiderationforusingVoronoiesquediagramsisdeterminingthelocationforgeneratorpoints. (t)

4.3 DeterminingGeneratorPointsUsing PopulationDensityDis-

tributions

Fornow,wehavedefinedhowtogenerateregionsgivenasetofgeneratorpoints.HereweconsiderhowtodefinethegeneratorpointsinordertocreateVoronoiandVornoiesquediagrams.InthecaseofVoronoidiagrams,thisisouronlydegreeoffreedomsincegen-

eratorpointsgenerateuniqueVoronoiregions.Wefoundnowelldefinedalgorithmtodo

this,butinsteadcameupwithaprocedurethatfunctionsdecently.

Ourfirstapproachistoplacegeneratorpointsatthemlargestsetofpeaksthatarewelldistributedthroughout the state,(wherem is the required number of districts inthatstate).Bychoosinggeneratorpointsinthisway,wekeeplargercitieswithintheboundarieswewillgeneratewithVoronoiorVornoiesquediagramsandwemakesure

thegeneratorpointsarewelldispersedthroughoutthestate.Oneproblemthatarisesiswhencitiesaresolargethatinorderfordistrictstoholdthesameamountofpeople,acity

mustbedividedintodistricts.Aperfectexample isNewYorkCity, whichcontainsenough peopletohold13districts.Takinglargecitiesintoaccounttakesextraconsideration.

Oursecondapproachistochoosethelargestpeaksinthepopulationdistributionandassigneachpeakwithaweight.Theweightforeachgeneratorpointisthenumberofdistrictsthepopulationsurroundingthatpeakneedsto bedividedinto.We callthisweightthedegeneracyofthegeneratorpoint.Webeginassigninggeneratorpointstothehighestpopulatedcitieswiththeircorresponding

degeneraciesuntilthesumofallthegeneratorpointsandtheirrespectivedegeneraciesisequaltom. Inotherwords,until:

Team1034 Page10of21

Figure3:Illustrationofcreatingdivisionsbyfirstsubdividingthemap.Left:Populationdensitydistributionofhypotheticalmapwithfivedesireddistricts.Middle:Asubdivisionofthemapintotworegionsgeneratedfromtwounshowngeneratorpoints.Right:Finaldivisionofeachsubregionfromthemiddlefigureintodesiredfinaldivisions.

「 allgenerator pts. degeneracyofgeneratorpt.=m

AswewillseewhenweapplyourmodeltoNewYork,thismethodworkswell.Itshouldbenoted,though,thatthisis nottheonlywaytodefinethelocationofgeneratorpoints,butitisaverygoodstart. 4.4 ProcedureforCreatingRegionsusingVoronoiandVoronoiesqueDiagrams

Oncewehaveourgeneratorpoints,wecangenerateourdiagramswithtwomoresteps:firstgeneratethediagramusingthegivengeneratorpoints.Withineachgeneratedregion,

calledasubdivision,withsomedegeneracyr,creaternewgeneratorpointswithinthatsubdivisionbyfindingtherlargestpopulationdensitypeaksandcreateanotherdiagram.Seefig.3

5 RedistrictinginNewYorkState

Atthispoint,wehavedescribedageneralprocedureforgeneratingpoliticaldistrictswithVoronoidiagramswhichseemseffective.WenowturnourattentiontotestingourmodelsonNewYork. ? hasregionswithlargepopulationdensity,

? hasregionswithconstrainedgeography,

? andmustbedividedintomany(29)regions.

Team1034 Page11of21

Webeginbyexplainingourmethodforchoosinggeneratorpointsatpopulationcenters,sincethesepointswilluniquelydetermineaVoronoidiagramforthestate.ThenwedescribeseveralmethodsforgeneratingVoronoiandVoronoiesquediagramsfromthesepointsandpresentthecorrespondingresults.Finallywediscusshow

tousethesediagramstocreateactualpoliticaldistrictsforNewYorkstate.

5.1 PopulationDensityMap

ToapplyourVoronoidiagrammethodstoNewYork,wefirstobtainanapproximatepopulationdensitymapofthestate.TheU.S.CensusBureaumaintainsadatabase[2]whichcontainscensustract-

levelpopulationstatistics;whencombinedwithboundarydata[1]foreachtract,it‘spossibletogenerateadensitymapwitharesolutionnocoarserthan 8,000people perregion[7].Unfortunately,ourlimitedexperiencewiththeCensusBureau‘sdataformatpreventedusfromaccessingthisdatadirectly,andwecontentedourselveswitha792-by-

660pixelapproximationtothepopulationdensitymap[6].

WeloadedthisrasterimageintoMATLABandgenerated asurface plotwhereheight represented populationdensityateachpoint. Toremoveartifactsintroduced byusing acoarse latticerepresentationforfinely-distributeddata,we applieda6-pixelmoving averagefiltertothedensitymap.Theresultingpopulationdensityisshowninfig.4.

5.2 LimitationsoftheImage-BasedDensityMap

Thepopulationdensityimageweusedyieldedadensityvalueforeverythirdofasquaremilefromthefollowingset(measuredinpeoplepersquaremile):

{0, 10, 25, 50,100, 250,500, 1000,2500, 5000}.

Thisprovidesadecentapproximationforregionswithadensitysmallerthan5,000people/sq.mi. However,sinceNewYorkCity‘saveragepopulationdensityis26,403people/sq.mi.[10],theapproximationwillbreakdownatlargepopulationcenters.

5.3 SelectingGenerator Points

Ourcriteriaforredistrictingthestatestipulatesthattheregionswegenerate

mustcontainequalpopulations.

NewYorkstatemustbedividedinto29congressionaldistrictsto

supportitsshareofrepresentatives,soeachregionmustcontain≈3.45%ofthestate‘s population. Sinceastate‘spopulationisconcentratedprimarilyinasmallnumberof

cities,weuselocalmaximaofthepopulationdensitymapascandidatesforgeneratorpoints.

Ifweweretosimplychoosethehighest29peaksfromthepopulationdensity mapas

oursetofgeneratorpoints,theresultingsetwouldbecontainedentirelyinthelargestpopulationcentersandwouldnotbewelldistributedevenlyoverstate.Forthelargestpopulationcenters,weassignasinglegeneratorpointwithadegeneracyasdescribedin

4.3. Afterallthegeneratorpointshavebeenassigned,wegenerateaVoronoidiagramforthestate.Then,wereturntotheregionswithdegenerategeneratorpointsandrepeattheprocessoffindinggeneratorpointsforthatregionandgenerateaVoronoidiagramfromthem.Seefig.3foranillustrationofthedecompositionbeforeandaftersubdivision.

Team1034 Page12of21

(a) TopView:

WhiteareasrepresenthighpopulationdensityoverNewYor

k

(b) AngledView:ClearerviewofpopulationdistibutionoverNewYork

Figure4:NewYorkStatepopulationdensitymap.Dataobtainedfroma792-by-

660pixelrasterimage;colorandheightindicatetherelativepopulationdensityateachpoint.

Team1034 Page13of21

(a) RegionscreatedusingtheManhattanmetricbeforesubdivisionsareim-

plemented.

(b) Regions createdusingtheManhattanmetricaftersubdivisionsareimple-

mented.SubdivisionsarecreatedinNewYorkCity,Buffalo, Rochester,

andAlbany

Figure5:DepictionoftheimplamentationofVoronoidiagramswiththeManhattanmetricinthethreestepprocessof:assigningdegeneraciestogeneratorpoints,usingthedegener-

atepointstogenerateregionsusingtheVoronoidiagrammethod,andcreatingsubregionsof the regionsgeneratedby degeneratepoints.Only thelast two stepsare depicted.Theprocess forVoronoiesquediagramsisthesame.(Dotsineachregionrepresentgeneratorpointlocations.)

Team1034 Page14of21

BasedonourdensitydataforNewYorkstate,wesubdividetheregionaroundNewYorkCityinto12subregions,Buffalointo3subregions,andRochesterandAlbanyinto2subregions.Notethatthisroughlycorrespondstothecurrentallocation,whereNewYorkCityreceives14districts,Buffalogets3,andRochesterandAlbanybothgetroughly2.Here,NewYorkCity‘s population isunderestimatedsincetheaveragedensitytherefarexceedsour data‘sdensityrange.Withamoredetailed dataset,our methodwouldhavecalledforthecorrectnumberofsubdivisions.

5.4 ApplyingVoronoiDiagramstoNY

Thesimplestmethodweconsiderforgeneratingcongressionaldistricts istosimplygen-eratethediscreteVoronoidiagramfromasetofgeneratorpoints.Weachievethisbyiteratively ?growing‘regions outward with the function fconstant.That waytheregionsgrowataconstantrate,andhencetheresultingdiagramisvoronoi.Aregion‘sgrowth

islimitedateachstepbyitsradiusinacertainmetric;weconsideredtheEuclidean,Manhattan,anduniformmetrics.Oncetheinitialdiagramhasbeencreated,anewsetofgenerator pointsfordenseregionsarechosenandthose regionsaresubdivided usingthesamemethod.Unrefineddecompositionscanbeseeninfig.6.

Eachmetricproducesarelativelysimpledecompositionofthestate,thoughtheMan-hattanmetrichassimplerboundariesandyieldsaslightlysmallerpopulationvariancebetweenregions.

5.5 ApplyingVoronoiesqueDiagrams toNY

ThoughoursimpleVoronoidiagramsproducedsimpleregionswithapopulationmeannearthedesiredvalue,thepopulationvariancebetweenregionsisenormous.Inthissense,thesimpleVoronoidecompositiondoesn‘tmeetoneofthemainpartsofourredistrictinggoal.

However,theVoronoiregionsaresosimplethatweprefertoaugmentthismethodwithpopulationweightsratherthanabandonitentirely.

Fig.7showstheresultofthisdecomposition,alongwithexplodedviewsofthetworegionswhichweresubdividedmorethantwiceintherefinementstageofthediagramgeneration.Thepopulationcontainedineachregionissummarizedintable1.

Table1:PopulationFractionineachLegislativeDistrict

Team1034 Page15of21

(a) Regionscreated usingtheManhattanmet-

ricbeforesubdivisions. AveragePopulation

=(3.5±2.2)%.

(b) RegionscreatedusingtheEuclideanmet-ricbeforesubdivisions. AveragePopulation =(3.7±2.6)%.

(c) RegionscreatedusingtheUnifrommet-

ricbeforesubdivisions. AveragePopulation

=(3.7±2.6)%.

Figure6:

Voronoidiagramsgeneratedwiththreedistancemetricsbeforesubdivisionofdenselypopulatedregions.(Dotsineachregionrepresentgeneratorpointlocations.)

Team1034 Page16of21

(a) OverallNewYorkVoronoiesqueregions

(b) ExplodedviewofregionsaroundBuffalo. (c)ExplodedviewofregionsaroundLongIs- land. Figure7:DistrictscreatedbytheVoronoiesquediagramforNewYorkstate. Averagepopulationperregion=(3.34±0.74)%.(Dotsineachregionrepresentgeneratorpoint locations.)

Team1034 Page17of21

5.6 PreciselyDefiningBoundaryLines

Itisnotsatisfactorytosaytheregionscreatedbyourmodelsshoulddefinethefinalboundarylocations.Intheleast,boundariesshouldbetweakedsothattheydon‘tacci-

dentalydividehousesintotwodistricts.However,giventhescaleatwhichtheVoronoiandVoronoiesquediagramsweredrawn,itseemsreasonabletoassumethattheirbound-

ariescouldbemodifiedtotraceexistingboundaries—

likecountylines,ZIPcodes,orcitystreets—

withoutchangingtheirgeneralshapeoraveragepopulation appreciably.Asan

example,theaverageareaofaZIPcodeinNewYorkstateis≈10sq.mi.androughly200 cityblockspersquaremileinManhattan,whiletheminimumsizeofoneofourVoronoiregionsis73sq.mi.andtheaveragesizeis≈2,000sq.mi..Thereforeitseemsreasonable thatwecouldapproximatetheboundaries

ofourVoronoiand/orVoronoiesquediagramsbypreexistingboundaries.

6 Analysis 6.1 NewYorkStateResults

We turnnowtoa discussionof howwell ourresultsfromtheprevioussectionmeetouroriginalspecificationforredistricting.Intermsofsimplicityofgenerateddistricts,ourVoronoidiagrammethodisaclearwinner,particularlywhenappliedwiththeManhattanmetric:thegeneratedregionsarecontiguous

andcompactwhiletheirboundaries,beingunionsoflinesegments,areaboutthesimplestthatcouldbeexpected.However,thismethodfallsshortinachievingequalpopulationdistributionamongtheregions,sincethevarianceintheaveragepopulationperregionisontheorderoftheaveragepopulationitself.

Asmaybeexpectedinanysortofhigh-

dimensionaloptimizationproblem,thereisanessentialtradeoffinthisproblembetweenthesimplicityofthelegislativedistrictsandtheirrespectivepopulations.Accordingly,whenwemodifytheVoronoidiagrammethodtogeneratepopulation-

weightedVoronoiesqueregions,wecutthepopulationvarianceby

afactoroffour—from±2.8%to±0.7%—whilesufferingasmalllossinthesimplicity oftheresultingregions. Inparticular,regionsintheVoronoiesquediagramsappearto

belesscompactandtheirboundariesaremorecomplicatedthantheirVoronoidiagramcounterparts,thoughcontiguity is still maintained.

Finally,wenotedintheprevioussectionthatanyactualimplementationofadiagram

generatedfromeitherofourmethodswouldhavetomakesmall,localizedmodifications toensurethedistrictboundariesmakesensefromapracticalperspective.Thoughthiswould appeartoopenthedoorforthesamesortofpolitically-

biaseddistrictmanipulationsourmethodswereaimingtoavoidinthefirstplace,wethinkthesizeofthenecessarydeviations(ontheorderofmiles)issmallenoughwhencomparedtothesizeofaVoronoiorVoronoiesqueregion(ontheorderoftensorhundredsofmiles)tomaketheneteffectofthesevariationsinsignificant.Therefore,thoughwehaveprovidedonlyafirst-order

approximationtothecongressionaldistricts,wehaveleftlittleroomforGerrymanderingtooccur.

Team1034 Page18of21

6.2 GeneralResults

WealreadyknowhowwellourresultsworkedforNewYork.Howeffectiveisourmethodingeneral?Weexaminetheresultsforanarbitrarystateincludingworstcasescenariosforeachcriteria.

PopulationEquality

Thelargestproblemwiththisrequirementoccurswhenwetrytomakeregionstoosimple.

Typically,ourVoronoimethodhasthemostroomforerrorhere.Ifastatehasaseriesofhighpopulationdensitypeakswitharelativelyuniformdecreaseinpopulationdensity

extendingawayfromeachpeak,thentheregionswilldifferquiteabit.Thisisbecauseinthissituation,ratiosofpopulationsarethenroughlyequaltotheratiosofareasbetweenregions.However,ourfinalmethodfocusesprimarilyonpopulationsoequalityismucheasiertoregulatehere.

Contiguity

Contiguityproblemsariseoftenifthestateitselfhaslittlecompactness,likeFlorida,orifthestatehassomesortofsoundlikeWashington.Thefirsttwomethodsfocusmore

onpopulationdensitywithoutreallyacknowledgingtheboundariesofthestateitself.Soit‘spossibleforoneregiontobeseparatedbysomegeographicobstructionlikeabodyofwateroramountainrange.Againthefinalmethodfixesthisbygrowinginincrements,thisallowsforstateboundariestobedefined.Thenregionswouldn‘tgrowoverbutaroundspecifiedobstacles.

Compactness

Unfortunately,thefinal methoddoesn‘tdo everything,it istheleastlikelycandidateforgeneratingcompactregions.Thefirsttwoaremostsuccessfulinthisarea.Thefirstmethodcreatesallconvexregions.Thoughthesecondcan‘tguaranteeconvexity,itsformissimilarinshapeandsizetothefirst.Furthermore,onenicepropertyofthegeneratedregionsfromthefirstmethodisthatthereisawaytomakeslightadjustmentstothe boundarieswhilestillmaintainingconvexity(see §7.1)Thisisgoodfortakingpopulation shiftsacrossdistrictsintoaccountbetweenredistrictingperiods.

7 ImprovingtheMethod

Nowthattheproblemareashavebeendefined,weoffersomewaystoreducetheeffectoftheseproblems.

7.1 Boundary Refinement

ConsidertheVoronoidiagrammethod.Weknowthisapproachisgoodatgeneratingpolygonaldistrictsbutnotassuccessfulatmaintainingpopulationequality.Onesuchmethodthathelpsisvertexrepositioning.Noticethatadjacentdistrictsgeneratedbythismethodallshareavertexcommontoatleastthreeboundaries.Fromthisvertexextends

Team1034 Page19of21

Figure8:IllustrationofVoronoidiagramgenerationwhichtakesgeographicobstaclesintoaccount.

afinitenumberoflinesegmentsthatpartiallydefinetheboundariesofthese

adjacentregions.Connectingtheendpointsofthesesegmentsyieldsapolygon.Nowwearefreetomovethecommonvertexanywhereintheinteriorofthispolygonwhilestillmaintainingconvexity.Withthiswecanredrawboundaries betweenregions thataresignificantlydifferentinpopulationsizeandindoingsohelpequalizeeachoftheregions. TherearealsowaystoadjustpopulationinequalityintheVoronoiesquemethod.Lookingattheregionwiththelowestpopulation,systematicallyincreasetheareaofthelow-

populationregionswhiledecreasingtheareaoftheneighboringhigh-populationregions.

7.2 GeographicObstacles

Ourmethoddoesn‘timplementgeographicareassuchasrivers,mountains,canyons,andotherprominentfeatures.TheVoronoiesquemethod,however,hasthepotentialtoim-

plimentthesefeatures.Thesamealgoriththatdetectsintersectionsbetweenvornoiesqueregionscandetectadefinedgeographicboundaryandstopgrowinginthatdirection.Anillustrationofthisideaisshowninfig.8.Thesegeographicobstacleswouldbechosenby theredistrictingcommittee.

8 BulletintotheVotersoftheStateofNewYork

READONFORIMPORTANTINFORMATIONREGARDINGYOURREP-RESENTATIVE GOVERNMENT

Authoritieswithinyourstate‘sgovernmentrecentlyrealizedthatduringreapportionment— theprocessbywhichyourstate‘snumberofcongressionalrepresentativeschanges—

theincumbentpolitical

leaderstendtoGerrymandertheboundariesofcongressionaldistricts,redrawingthemtoinfluencefutureelectionsintheirfavor.Asthiscanundermineequalrepresentationforallcitizens,theStateofNewYorkcommissionedaninterdisciplinaryteamofmathematiciansandengineerstocreateanobjectiveprocedureforredistrictingthatcanbeappliedinthefuturetopreventpartisaninfluenceovercongressionaldistrictboundaries.

Team1034 Page20of21

Theteamcame to theconclusion thattobefairto all,congressional districts should: ? beconnected,

? containequalpopulations,

? beascompactaspossible, and

? notunnecessarilysubdividelargecities.

Accordingly,theycreatedasimplemethodforgeneratingdistrictsthatmeetthesecriteria. ThemethodisbasedonageometricalstructureknownasaVoronoidiagram,which

describesapartitionofyourstateintocompact,connectedregionsgeneratedfromasetofinitialpoints;seefigure1foranexample.Sincetheregionsaresupposedtoenvelopequalpopulations,theinitial

pointswerechosenatmajorpopulationcenters(likeNewYorkCity,Buffalo,Rochester,andAlbany,amongothers).Theregionsarethen?grown‘outfromthesepopulationcentersas infigure2untiltheentire stateiscovered.

Toensurethedistrictsendupwithroughlyequalpopulations,aregions‘growthislimitedbythepopulationcontainedwithinit.Thisresultsinafinaldiagramwhichhasconnected,compactregionswithsmallpopulationvariation.Inotherwords,diagramsgeneratedwiththismethodfulfilltheguidelinesforcreatingfairlegislativedistricts.

Thenewdistrictdiagramisillustratedinfigure7.Thisdiagramiscomposedof29distinctcongressionaldistricts,eachofwhichcontainscloseto3.4%ofthetotalstatepopulation.Butmoreimportantthantheprecisepopulationcontainedineachregionisthefactthatthedistrictsweregeneratedobjectivelybyacomputerizedmethod,sopartisanpoliticsplayno rolein the result.Thisensuresthatthe

nexttimeboundarylinesaredrawn,theywillprovideanimpartialpartitionofourstate‘spopulation,withnoroom forGerrymandering.

9 Conclusion

Therearemanymethodsinexistencefordrawingdistrictboundaries.Mostofthesemod-

elsaresuccessfulinwhatissetsouttodo.However,manyofthemdependoncurrentstatedivisionsasastartingpointsforcreatingdistricts.Ourmodeldiffersinthatweonlyrequiretheuseofastate‘spopulationdistributionandasanoptioncanincorporatecounty,property,andgeographicconsiderations.

OurVoronoiesquemodelsatisfiesourproposedgoal.Wesupplyamodelforare-

districtingcommitteetogeneratedistrictboundariesthataresimple,contiguous,andproducedistrictswithequalpopulations.Inparticular,wefoundthatVoronoiesquedia-

gramsredistrictNewYorkverywell.What‘sparticularlyattractiveaboutallthemethodsisthatgeneratingthedistrictsisintuitiveandaccessibletothegeneralpublicandalsothecomputergenerationprocesstakeslessthan10secondstocomplete.

References

[1]U.S.CensusBureau.2005firsteditiontiger/linedata,Feb.2007.

Team1034 Page21of21

[2]U.S.CensusBureau.Summary1file:Census2000,Feb.2007.

[3]Garfinkel,R.S.andNemhauser,G.L.Optimalpoliticaldistrictingbyimplicitenu-

merationtechniques.ManagementScience,16(8):B495–B508,apr1970.

[4]HowardD.Hamilton.ReapportioningLegislatures.CharlesE.MerrilBooks,Inc.,1966.

[5]Hess,S.W.,Weaver,J.B.,Siegfeldt,H.J.,Whelan,J.N.,andZitlau,P.A.Nonpar-

tisanpoliticalredistrictingbycomputer.OperationsResearch,13(6):998–

1006,nov1965.

[6]JimIrwin.Wikipedia.org:Newyorkpopulationmap,Feb.2006.[7]Niels

enMedia.Glossaryofmediaterms,Feb.2007.

[8]Mehrotra,Anuj,Johnson,EllisL.,andNemhauser,GeorgeL.Anoptimizationbasedheuristicf

orpoliticaldistricting.ManagementScience,44(8):1100–1114,aug1998.

[9]PeterJ.Taylor.Anewshapemeasureforevaluatingelectoraldistrictpatterns.TheAmericanPol

iticalScienceReview,67(3):947–950,sep1973.

[10]Wikipedia.org.Newyorkcity,Feb.2007.

[11]H.P.Young. Measuringthecompactnessoflegislativedistricts.

LegislativeStudiesQuarterly,13(1):105–115,feb1988.

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com