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

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.

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