Optimal facility location under various distance functions

SergeiBespamyatnikh1,KlaraKedem2,3andMichaelSegal2

DepartmentofComputerScience

UniversityofBritishColumbia,Vancouver,B.C.CanadaV6T1Z4DepartmentofMathematicsandComputerScience

Ben-GurionUniversityoftheNegev,Beer-Sheva84105,IsraelComputerScienceDepartment

CornellUniversity,UpsonHall,CornellUniversity,Ithaca,NY14853

3

2

1

September30,1999

Abstract

Wepresentefficientalgorithmsfortwoproblemsoffacilitylocation.Inbothproblemswewanttodeterminethelocationofasinglefacilitywithrespecttongivensites.Inthefirstweseekalocationthatmaximizesaweighteddistancefunctionbetweenthefacilityandthesites,andinthesecondwefindalocationthatminimizesthesum(orsumofthesquares)ofthedistancesofkofthesitesfromthefacility.

1Introduction

Facilitylocationisaclassicalproblemofoperationsresearchthathasalsobeenexaminedinthecomputationalgeometrycommunity.Thetaskistopositionapointintheplane(thefacility)suchthatadistancebetweenthefacilityandgivenpoints(sites)isminimizedormaximized.

Mostoftheproblemsdescribedinthefacilitylocationliteratureareconcernedwithfindinga“desirable”facilitylocation:thegoalistominimizeadistancefunctionbetweenthefacility(e.g.,aservice)andthesites(e.g.,thecustomers).Justasimportantisthecaseoflocatingan“undesirable”orobnoxiousfacility.Inthiscaseinsteadofminimizingthelargestdistancebetweenthefacilityandthedestinations,wemaximizethesmallestdistance.Applicationsforthelatterversionare,e.g.,locatinggarbagedumps,dangerouschemicalfactoriesornuclearpowerplants.Thelatterproblemisunconstrainedifthedomainofpossiblelocationsforthefacilityistheentireplane.PracticallythelocationofthefacilityshouldbeinaboundedregionR,whoseboundarymayormaynothaveaconstantcomplexity.

Inthispaperweconsiderthefollowingtwoproblems:

1.Undesirablelocation.LetSbeasetofnpointsintheplane,enclosedinarectangularregionR.LeteachpointpofShavetwopositiveweightsw1(p)andw2(p).Findapointc∈Rwhichmaximizes

min{max{w1(p)·dx(c,p),w2(p)·dy(c,p)}},

p∈S

wheredx(c,p)definesthedistancebetweenthexcoordinatesofcandp,anddy(c,p)definesthedistancebetweentheycoordinatesofcandp.

2.Desirablelocation.GivenasetSofnpointsandanumber1≤k≤n−1findapointpsuchthatsumoftheL1(L∞)distancesfromptoallthesubsetsofSofsizekisminimized.Forthisproblemweconsidertwocases:thediscretecase–wherep∈S,andthecontinuouscasewherepisanypointintheplane.

ThefirstproblemisconcernedwithlocatinganobnoxiousfacilityinarectangularregionRundertheweightedL∞metric,whereeachsitehastwoweights,oneforeachoftheaxes.Anapplicationfortwo-weighteddistanceis,e.g.,anairpollutantwhichiscarriedfurtherbysouth-northwindsthanbyeast-westwinds.Fortheunweightedcaseofthisproblem,whereRisasimplepolygonwithuptonverticesandundertheEuclideanmetric,BhattacharyaandElgindy[4]presentanO(nlogn)timealgorithm.ForweightedsitesonecanconstructtheVoronoidiagramandlookfortheoptimallocationeitheronavertexofthisdiagramorontheboundaryoftheregionR.Unfortunately,forweightedsites,theVoronoidiagramisknowntohavequadraticcomplexityintheworstcase,anditcanbeconstructedinoptimalO(n2)time[2].Thus,theoptimallocation,usingtheVoronoidiagram,canbefoundinO(n2)time[9].ThefirstsubquadraticalgorithmfortheweightedproblemunderL∞metricandarectangularRregionwaspresentedbyFollertetal.[10].TheiralgorithmrunsinO(nlog4n)time.Inthispaperwepresenttwoalgorithmsforthetwo-weightedL∞metricprobleminarectangularregion..ThefirstonehasO(nlog3n)runningtimeanditisbasedontheparametricsearchingofMegiddo[11]whichcombinesbetweenthesequentialandtheparallelalgorithmsforthedecisionprobleminordertosolvetheoptimizationproblem.ThesecondalgorithmhasO(nlog2n)runningtime,andusesthedifferentoptimizationapproachthatisdescribedbeMegiddoandTamir[12].

Thesecondproblemdealswithlocatingadesirablefacilityunderthemin-sumcriterion.SomeapplicationsforthisproblemarelocatingacomponentinaVLSIchiporlocatingaweldingrobotinanautomobilemanufacturingplant.ElgindyandKeil[8]consideraslightvariationoftheproblemundertheL1metric:GivenapositiveconstantD,locateafacilitycthatmaximizesthenumberofsiteswhosesumofdistancesfromcisnotgreaterthanD.Theyalsoconsiderthediscreteandcontinuouscases.TheruntimesoftheiralgorithmsareO(nlog4n)forthediscretecaseandO(n2logn)forthecontinuouscase.OuralgorithmforthediscretecaserunsintimeO(nlog2n),andforthecontinuouscaseinO((n−k)2log2n+nlogn)time.

ItiswellknownthatthemetricsL1andL∞aredualintheplane,inthesensethatnearestneighborsunderL1inagivencoordinatesystemarealsonearestneighborsunderL∞ina45degreesrotatedcoordinatesystem(andviceversa).Thedistances,however,aredifferentbyamultiplicative√factorof

2Undesirablefacilitylocation

Inthissectionwefirstpresentasequentialalgorithmthatanswersadecisionqueryoftheform:givend>0,determinewhetherthereexistsalocationc∈Rwhosex-distancefromeachpointpi∈S(thedistancebetweenthexcoordinatesofcandpi)is≥d·w1(pi),andwhosey-distancetothepointsofSis≥d·w2(pi).Wewillusethissequentialalgorithminordertoobtaintwodifferentalgorithmsforsolvingourproblem.

Thefirstisbasedontheparametricsearchoptimizationscheme[11]and,tus,weprovideaparallelversionofthedecisionalgorithminordertouseit.LetTsdenotetheruntimeofthesequentialdecisionalgorithm,andTp,resp.P,thetimeandnumberofprocessorsoftheparallelalgorithm;thentheoptimalsolution(apointcthatmaximizesd)canbecomputedinsequentialtimeO(PTp+TsTplogP)[11].

Thesecondusesanotheroptimizationapproach,proposedin[12].Themainideaistorepresentasetofpotentialsolutionsinacompact,efficientway,useaparallelsortingschemeandthenlookforoursolutionbysomekindofabinarysearch.TherunningtimeofthealgorithmisO(Tslogn).

2.1Thesequentialalgorithm

Theformulationofthedecisionproblemaboveimpliesthateachpointpi∈Sdefinesaforbiddenrectangularregion

Ri={r∈R2|dx(r,pi)whereccannotreside.DenotebyURtheunionofalltheRi.AnadmissiblelocationforcexistsifandonlyifR∩UR=∅.Inotherwords,wearegivenasetofnrectanglesRiandwanttofindwhetherURcoversR.WheneachpointhasthesameweightinbothaxesthenthecombinatorialcomplexityoftheboundaryofURislinear.InourcasetheboundaryofURhasO(n2)verticesintheworstcase.

TheproblemoffindingwhetherasetofnrectanglescoversarectangularregionRhasbeensolvedinO(nlogn)timeusingthesegmenttreeT[13].Weoutlinethiswellknownsequentialalgorithmforthesakeofclarityofourparallelalgorithm.

DenotebyL={x1,...x2n}thexcoordinatesoftheendpointsofthehorizontalsidesoftherectangles.WecalltheelementsofLtheinstancesofT.Similarly,letM={y1,...y2n}bethelistofycoordinatesoftheendpointsoftheverticalsidesoftherectangles.Assumeeachlistissortedinascendingorder.TheleavesofthesegmenttreeTcontainelementarysegments[yi,yi+1),i=1,...,2n−1,intheirrangefield.TherangeateachinnernodeinTcontainstheunionoftherangesinthenodesofitschildren.

AverticallineissweptovertheplanefromlefttorightstoppingattheinstancesofT.Ateachinstancex,eitherarectangleisaddedtotheunionoritisdeletedfromit.Theverticalsidevofthisrectangleisinsertedto(ordeletedfrom)T(visstoredinO(logn)nodesandisequaltothedisjointunionoftherangesofthesenodes).TheupdateofTatinstancexinvolvesmaintainingacovernumberinthenodes.Thecovernumberatanodecountshowmanyverticalrectanglesidescovertherangeofthisnodeanddonotcovertherangeofitsparent.IfatdeletingarectangletheheightofRisnotwhollycoveredbyalltheverticalsegmentsthatarecurrentlyinT,thentheanswertothedecisionproblemis“yes”.Namely,wefoundapointinRwhichisnotinUR,andwearedone.Iftheansweris“no”thenweupdateTandproceedtothenextinstance.ThusLemma1Givenafixedd>0wecancheckinO(nlogn)time,usingO(n)space,whetherthere

3

existsapointc∈R,suchthatforeverypointpi∈Sthefollowingholds:dx(c,pi)·w1(pi)≥danddy(c,pi)·w2(pi)≥d.

2.2Theparallelversionandtheoptimization

Nextwepresenttheparallelalgorithmwhichwebelieveisofindependentinterest.InordertoproduceanefficientparallelalgorithmforthedecisionproblemweaddsomeinformationintothenodesofT.Thisinformationencapturesthecoverinformationateachnode,aswillbeseenbelow.

LetL={x1,x2,...,x2n}bethelistofinstancesasabove.LettheprojectionofarectangleRjonthexaxisbe[xi,xk].WeassociatewithRjalife-spanintegerintervallj=[i,k].LetvjbetheprojectionofRjontheyaxis.TheintegerintervalljdefinestheinstancesatwhichthesegmentvjisstoredinTduringthesequentialalgorithm.WeaugmentTbystoringthelife-spanofeachverticalsegmentvjintheO(logn)nodesofTthatvjupdates.WefurtherprocesseachnodeinTsothatitcontainsalistofcovertwolife-ranges.Thisisalistofintervalsconsistingofthepairwiseintersectionsofthelife-spansinthenode.Forexample,assumethatanodescontainsthelife-spans[1,7],[3,4]and[5,6].Thelistofcovertwoatsis[3,4]and[5,6].Ifaverticalsegmentistobedeletedfromsatinstancesx1,x2orx7,thenswillbeexposedafterthedeletion.Butifthedeletionoccursatinstancex3,x4,x5orx6then,sincethecoverofsis2atthisinstance,swillnotbeexposedbydeletingvj.

Ourparallelalgorithmhastwophases:phaseIconstructstheaugmentedtreeTandphaseIIcheckswhetherRgetsexposedatanyofthedeletioninstances.

PhaseIThesegmenttreeTcanbeeasilybuiltinparallelintimeO(logn)usingO(nlogn)processors[1].UnlikeinLemma1above,wherewestoreineachnodejustthecovernumber,herewestoreforeachsegmentitslife-spaninO(logn)nodes.ThusToccupiesnowO(nlogn)space[13].Addingthecovertwolife-spanintervalsisperformedasfollows.

Wesortthelistoflife-spansateachnodeaccordingtothefirstintegerintheintervalthatdescribesalife-span.Wemergethelistoflife-spansateachnodeasfollows.Iftwoconsecutivelife-spansaredisjointwedonotdoanything.Assumethetwoconsecutivelife-spans[k1k2]and[g1,g2]overlap.Weproducetwonewlife-ranges:

(a)thelife-rangeofcoveratleastone–[k1,max(k2,g2)]and(b)thelife-rangeofcoveratleasttwo–[g1,min(k2,g2)].

Wecontinuetomergethecurrentlife-rangeofcoveratleastonefromitem(a)abovewiththenextlife-spaninthelisttillthelistoflife-spansisexhausted.Wenextmergethecovertwolife-rangesintoalistofdisjointintervalsbytakingtheunionsofoverlappingintervals.Atthisstageeachnodehastwolistsoflife-ranges.ButthisdoesnotsufficeforphaseII.Foreachnodewehavetoaccumulatethecoverinformationofitsdescendants.Startingattheleaveswerecursivelyprocessthetwolistsoflife-rangesatthenodesofTseparately.Wedescribedealingwiththelistofcoverone.Assumethetwochildrennodesofanodescontainintersectinglife-ranges,thenthisintersectionintervalisanintervalofinstanceswherealltherangeofsiscovered.Wecopytheintersectionintervalintothenodes.Whenwearedonecopyingwemergethecopiedlistwiththenode’slife-spanlistasdescribedabove,andthenmergethelistofcovertwowiththecopiedlistofcovertwo,byunioningoverlappingintervals.

PhaseII.Ourgoalinthisphaseistocheckinparallelwhether,uponadeletioninstance,theheightofRisstillfullycoveredorapointonitisexposed.Wedoitasfollows.AssumethattheverticalsegmentvisdeletedfromTatthejthinstance.WegodownthetreeTinthenodesthat

4

storevandcheckwhetherthelife-spanlistsatallthesenodescontaintheinstancejintheirlistofcovertwo.Iftheydothen(theheightof)Risnotexposedbydeletingv.Complexityofthealgorithm.

Itiseasytoshowthatthelife-rangelistsdonotaddtotheamountofrequiredstorage.Thenumberofinitiallife-spanintervalsisO(nlogn).Thenumberofinitiallife-rangesofcovertwocannotbegreaterthanthat.Ithasbeenshown[7]thatcopyingthelistsinthenodesinthesegmenttreetotheirrespectiveancestorsdoesnotincreasetheasymptoticspacerequirement.TheaugmentationofTisperformedinparalleltimeO(logn)withO(nlogn)processorsasfollows.WeallocateatotalofO(nlogn)processorstomergethelife-spanrangesinthenodesofT,puttingateachnodeanumberofprocessorswhichisequaltothenumberoflife-spanrangesinthenode.Thusthesortingandmergingofthelife-spanrangesisperformedinparallelintimeO(logn).

ThecheckingphaseisperformedinparallelbyassigningO(logn)processorstoeachdeletioninstance.Forthedeletionofaverticalsegmentv,oneprocessorisassignedtoeachnodethatstoresv.Theseprocessorsperforminparallelabinarysearchonthecovertwolife-rangesofthesenodes.ThusthecheckingphaseisperformedintimeO(logn).

Summingupthestepsoftheparallelalgorithm,wegetatotalofO(logn)parallelruntimewithO(nlogn)processorsandO(nlogn)space.Pluggingthisalgorithmtotheparametricsearchparadigm[11]weget

Theorem2GivenasetSofnpointsintheplane,enclosedinarectangularregionR,andtwopositiveweightsw1(p)andw2(p)foreachpointp∈S,wecanfind,inO(nlog3n)time,apointc∈Rwhichmaximizes

min{w1(p)·dx(c,p),w2(p)·dy(c,p)}.

p∈S

2.3Anotherapproach

BycarefullylookingattherespectiveVoronoidiagramwehavethefollowingcrucialobservation.Observation3Assumethattheoptimalsolutionisnotattainedontheboundaryoftherectangle.Then,w.l.o.g.,thereisanoptimalpointc,andtwopointspandqsuchthateither

w1(p)dx(c,p)=w1(q)dx(c,q)=optimalvalue,

or

w2(p)dy(c,p)=w2(q)dy(c,q)=optimalvalue.

Theaboveobservationwithagivenassumptionimpliesthattheoptimalvalueisanelementinoneofthefollowingfoursets:

S1={(px+qx)/(1/w1(p)+1/w1(q)):p,q∈S}S2={(px−qx)/(1/w1(p)−1/w1(q)):p,q∈S}S3={(py−qy)/(1/w2(p)−1/w2(q)):p,q∈S}S4={(py+py)/(1/w2(p)+1/w2(q)):p,q∈S}.

MegiddoandTamir[12]describehowtosearchfortheoptimalvaluer∗withinasetoftheform:S′={(ai+bj)/(ci+dj):1≤i,j≤n}.Thustherewillbegiven4nnumbersai,bj,ci,dj(1≤i,j≤n),andwewillhavetofindtwoelementss,t∈S′suchthatsSetSconsistsofthepointsofintersectionofstraightlinesy=(cix−ai)+(djx−bj)withthex-axis.Thesearchwillbeconductedintwostages.Duringthefirststagewewillidentifyaninterval[s1,t1]suchthats15

Stage1.Wesearchforr∗amongthepointsofintersectionsoflinesy=cix−aiwitheachother.Themethodisbasedonparallelsortingscheme.Imaginethatwesorttheset{1,...,n}bythe(cix−ai)’s,wherexisnotknownyet.Wheneveraprocessorhastocomparesomecix−aiwithcjx−aj,wewillinouralgorithmcomputethecriticalvaluexij=(ai−aj)/(ci−cj).WeusePreparata[14]parallelsortingschemewithnlognprocessorsandO(logn)steps.Thus,asinglestepinPreparataschemegivesrisetotheproductionofnlognpointsofintersectionoflinesy=cix−aiwitheachother.Giventhesenlognpointsandaninterval[s0,t0]whichcontainsr∗,wecaninO(nlogn)timenarrowdowntheintervalsothatitwillstillcontainr∗butnointersectionpointinitsinterior.Thisrequiresthefindingofmediansinsetsofcardinalitiesnlogn,1

4nlogn,...plusO(logn)evaluationsofthesequentialalgorithmforthedecisionproblem.Sincetheoutcomesofthecomparisonssofarareindependentofxintheupdatedinterval,wecanproceedwiththesortingeventhoughxisnotspecified.TheeffortperstepishenceO(nlogn)andtheentireStage1takesO(nlog2n)time.

Stage2.Whenthesecondstagestartswecanssumew.l.o.g.thatforx∈[s1,t1]cx−ai≤ci+1−ai+1,i=1,...,n−1.Letj(1≤j≤n)befixedandconsiderthesetSjofnlinesSj={y=cix−ai+djx−bj,i=1,...,n}.SinceSjis“sorted”over[s1,t1],wecanfindin

j

O(logn)evaluationsofthesequentialalgorithmforthedecisionproblemasubinterval[sj1,t1]suchj∗thatsj1j

Attheendofsecondstagewehavethevalues{sj1}and{t1},j=1,...,n.Definings=j∗′max1≤j≤n{sj1}andt=min1≤j≤n{t1}weobtainsThecasewiththeoptimalsolutionattainedontheboundaryoftherectanglebetreatedassubcaseofapreviouscase.Thusweconcludebyatheorem.

Theorem4GivenasetSofnpointsintheplane,enclosedinarectangularregionR,andtwopositiveweightsw1(p)andw2(p)foreachpointp∈S,wecanfind,inO(nlog2n)time,apointc∈Rwhichmaximizes

min{w1(p)·dx(c,p),w2(p)·dy(c,p)}.

p∈S

3Thediscretedesirablefacilitylocationproblem

Thediscretemin-sumproblemisdefinedasfollows.GivenasetSofnpointsintheplaneandanumberk.FindapointinSsuchthatthesumofdistancesfromittoitsknearestneighborsinSisminimized.Ouralgorithmscompute,foreachpointofS,thesumofdistancesfromittoitsknearestneighborsinS,andoutputapointwhichminimizesthesum.Firstwedealwiththespecialcaseofthediscretemin-sumproblemwhenk=n−1.

3.1Thediscretemin-sumproblemfork=n−1

Thismin-sumproblemappearsin[3]withanO(n2)trivialsolution.BelowwepresentanalgorithmthatsolvesthisproblemfortheL1metricinO(nlogn)time.

6

TheL1metricisseparable,inthesensethatthedistancebetweentwopointsisthesumoftheirxandy-distances.Thereforewecansolvetheproblemforthexandy-coordinatesseparately.Weregardthexcoordinatespart.Wesortthepointsaccordingtotheirx-coordinates.Let{p1,...,pn}

x

bethesortedpoints.Foreachpi∈Swecomputethesumσiofthex-distancesfrompitothe

x

restofthepointsinS.Thisisperformedefficientlyasfollows.Forthepointp1wecomputeσ1by

x

computingandsummingupeachofthen−1distances.For1xx

assumethex-distancebetweenpi−1andpiisδ,thenσi=σi−1+δ·(i−1)−δ·(n−i+1).Clearly

x

thesumsσi(fori=1,...n)canbecomputedinlineartimewhenthepointsaresorted.We

y

computeσianalogously.Assumethepointp∈Sisithinthexorderandjthintheyorder.The

yx

sumofdistancesfromptothepointsinSisσij=σi+σj.Thepointwhichminimizesthissumisthesoughtsolution.

Theorem5GivenasetSofnpointsintheplanesortedinxdirectionandinydirections,wecanfindinlineartimeapointp∈SwhichminimizesthesumoftheL1distancestothepointsinS.

WecanextendthistheoremtothecasewherethedistancetobeminimizedisthesumofsquaredL2distancesfromapointtotherestofthepointsofS,sincetheseparabilitypropertyholdsfor

x,...,σx}aboveandletτx=󰀁n(x−x)2.Thethiscaseaswell.Assumewehavecomputed{σ1ij=1jni

recursionformulaforcomputingallthesquaredx-distancesiseasilycomputedtobe

x2

τix=τix−1−2δσi−1−nδ

wherethex-distancebetweenpi−1andpiisδ.

Corollary6GivenasetSofnpointsintheplane,sortedinxdirectionandinydirection,we

canfindinlineartimeapointpofSwhichminimizesthesumofsquaredL2distancestothepointsinS.

3.2Thegeneralcase

Weturntothediscretemin-sumproblemfor1≤k≤n−1.WedescribethealgorithmfortheL∞metric.Ithastwophases.Inthefirstphasewefind,foreachpointpi∈S,thesmallestsquareRicenteredatpiwhichcontainsatleastk+1pointsofS.WealsogetthesquaresizeλiwhichisdefinedashalfthesidelengthofRi.Inthesecondphasewecomputeforeachpi,i=1,...,n,thesumofthedistancesfromittothepointsofSinRiandpickiforwhichthissumisminimized.

Forthefirstphaseweapplyasimpleversionofparametricsearching.Assumeq=(qx,qy)∈SisthequerypointforwhichwewanttofindthesmallestsquareRwhichcontainsatleastk+1pointsofS.Foraparameterλ,denotebyR(λ)asquareofsizeλcenteredatq.WetestwhetherR(λ)containsatleastk+1pointsofSbyapplyingChazelle’s[5,6]orthogonalrangecounting.Namely,givenasetofnpointsintheplaneandanorthogonalrange,findthenumberofpointscontainedintherange.ChazelleproposesadatastructurethatcanbeconstructedintimeO(nlogn)andoccupiesO(n)space,suchthatarange-countinganswerforaqueryregioncanbeansweredintimeO(logn).

Clearlytheminimumvalueofλisthedistancefromthequerypointtoitskthnearestneighbor.Thuscandidatevaluesforλare|qx−px|and|qy−py|forallp=(px,py)∈S.Byperformingabinarysearchinthesets{px|p∈S,px>qx},{px|p∈S,pxqy}and{py|p∈S,py7

Lemma7GivenasetSofnpointsandapositiveintegerkInthesecondphasewecompute,foreachpointpi∈S,thesumofdistancesfrompitoitsknearestneighbors,namely,thepointsofSwhicharecontainedinRi.InordertocomputeefficientlythesumsofdistancesinallthesquaresRi,weapplytheorthogonalrangesearchingalgorithmforweightedpointsofWillardandLueker[15]whichisdefinedasfollows.Givennweightedpointsind-spaceandaqueryd-rectangleQ,computetheaccumulatedweightofthepointsinQ.Thedatastructurein[15]isofsizeO(nlogd−1n),itcanbeconstructedintimeO(nlogd−1n),andarangequerycanbeansweredintimeO(logdn).Weshowhowtoapplytheirdatastructureandalgorithmtoourproblem.

Letq∈Sbethepointforwhichwewanttocomputethesumofdistancesfromittoitsknearestneighbors.LetRbethesmallestsquarefoundforqinthefirstphase.ClearlyRcanbedecomposedintofourtrianglesbyitsdiagonalssuchthattheL∞distancebetweenallpointsofSwithinonetriangleis,wlog,thesumofxcoordinatesofthepointsofSinthistriangleminusthexcoordinateofqtimesthenumberofpointsofSinthistriangle.Moreprecisely,let∆ubetheclosedtrianglewhosebaseistheuppersideofRandwhoseapexisq.DenotebyσuthesumoftheL∞distancesbetweenthepointsin∆uandq,andbyNuthenumberofpointsofSu={S−q}∩∆u,then󰀂y

σu=pj−qy·Nu.

pj∈Su

Ourgoalinwhatfollowsistopreparesixdatastructuresfororthogonalrangesearchforweighted

points,asin[15],threewiththeweightsbeingthexcoordinatesofthepointsofSandthreewiththeycoordinatesasweights,andthentodefineorthogonalranges,correspondingtothetrianglesinRforwhichthesumsofx(y)coordinateswillbecomputed.

Weproceedwithcomputingσu.Letl1bethexaxis,l2bealinewhoseslopeis45◦passingthroughtheorigin,l3betheyaxisandl4alinewhoseslopeis135◦passingthroughtheorigin.Theselinesdefinewedges(seeFigure1(a)):(1)Q1–thewedgeofpointsbetweenl1andl2whosexcoordinatesarelargerthantheirycoordinates,(2)Q2–thewedgeofpointsbetweenl2andl3whoseycoordinatesarelargerthantheirxcoordinates,and(3)Q3–thewedgeofpointsbetweenl3andl4whoseycoordinatesarelargerthantheirxcoordinates.

Eachofthesewedgesdefinesadatastructure,asin[15].Observe,e.g.,thewedgeQ1.Wetransforml1andl2intocorrespondingaxesofanorthogonalcoordinatesystem,andapplythesametransformationonallthepointspi∈S.Weconstructtheorthogonalrangesearchdatastructureforthetransformedpointswiththeoriginalycoordinatesasweights.(SimilarlyweconstructdatastructuresforthepointsofStransformedaccordingtoQ2andQ3,respectively,fortheysums,andanothersetofthreedatastructuresforthexsums.)

WedenotebyQi(q)thewedgeQitranslatedbyq.DenotebyYi(q)thesumoftheycoordinatesofthepointsofSinQi(q),i=1,2,3.Then

󰀂

pj∈Su

pyj=(Y2(q)+Y3(q))−(Y2(q1)+Y3(q1))−Y1(q1)+Y1(q2),

whereq1=(qx−λ,qy+λ)andq2=(qx+λ,qy+λ)(seeFigure1(b)).Ifthesegment[q1,q2]contains

pointsofSwedefineq1andq2asq1=(qx−λ−ǫ,qy+λ+ǫ)andq2=(qx+λ+ǫ,qy+λ+ǫ)forsomesufficientlysmallǫ>0.

8

l3l4Q3Q2Q1l2q1Q3(q)Q2(q)q2Q1(q)l1q(a)(b)Figure1:(a)TheregionsQiand(b)Qi(q)

TocomputeNuwecanusethesamewedgerangesearchscheme,butwithunitweightsonthedatapoints(insteadofcoordinates).InasimilarwaywecomputethesumσdforthelowertriangleinR(σlandσrfortheleftandrighttrianglesinRrespectively)andthecorrespondingnumberofpointsNd(NlandNr).

ItispossiblethatRcontainsmorethank+1points–thishappenswhenmorethanonepointofSisontheboundaryofR.OurformulaforthesumoftheL∞distancesshouldbe

D=σu+σd+σl+σd−λ·(Nu+Nd+Nl+Nr−k−1).

Hence,thesecondphaseofthealgorithm,requiresO(nlogn)preprocessingtimeandspace,andthenO(log2n)querytimeperpointpi∈Stodeterminethesumofdistancestoitsknearestpoints.Thus,forbothphases,weconclude

Theorem8Thediscretemin-sumproblemintheplanefor1≤k≤n−1andunderL∞-metric,canbesolvedintimeO(nlog2n)occupyingO(nlogn)space.

4Thecontinuousdesirablefacilitylocationproblem

Thecontinuousdesirablefacilitylocationproblemisdefinedasfollows.GivenasetSofnpointsandaparameter1≤k≤n−1.FindapointcintheplanesuchthatthesumofdistancesfromctoitsknearestpointsfromSisminimized.WeconsidertheproblemwherethedistancesaremeasuredbytheL1metric.

WecreateagridMbydrawingahorizontalandaverticallinethrougheachpointofS.AssumethepointsofSaresortedaccordingtotheirxcoordinatesandaccordingtotheirycoordinates.DenotebyM(i,j)thegridpointthatwasgeneratedbytheithhorizontallineandthejthverticallineintheyandxordersofSrespectively.Bajaj[3]observedthatthesolutiontothecontinuousmin-sumproblemwithk=n−1shouldbeagridpoint.AsamatteroffactithasbeenshownthatforthisproblemthepointM(⌊n/2⌋,⌊n/2⌋)istherequiredpoint.(Whereforanevennthesolutionisnotuniqueandthereisawholegridrectanglewhosepointscanbechosenasthesolution.)

Fork9

Theorem9Thecontinuousmin-sumproblemcanbesolvedin(nlogn+(n−k)2log2n)timeforanypositivek≤n−1.

References

[1]M.Attalah,R.Cole,M.Goodrich,“Cascadingdivideandconquer:atechniquefordesigning

parallelalgorithms”,SIAMJournalonComputing,18(3)(1989),pp.499-532.[2]F.AurenhammerandH.Edelsbrunner“Anoptimalalgorithmforforconstructingtheweighted

Voronoidiagramintheplane”,PatternRecognition,17(2),1984,pp.251–257.[3]C.Bajaj,“Geometricoptimizationandcomputationalcomplexity”,Ph.D.thesis,Tech.Report

TR-84-629,CornellUniversity,1984.[4]B.Bhattacharya,H.Elgindy,“Anefficientalgorithmforanintersectionproblemandanap-plication”,Tech.Report86-25,Dept.ofComp.andInform.Sci.,UniversityofPennsylvania,1986.[5]B.Chazelle,“Filteringsearch:Anewapproachtoquery-answering”,SIAMJ.Comput.,

15(1986),pp.703–724.[6]B.Chazelle,“Afunctionalapproachtodatastructuresanditsuseinmultidimensionalsearch-ing”,SIAMJ.Comput.,17(1988),pp.427–462.[7]B.ChazelleandH.EdelsbrunnerandL.GuibasandM.Sharir“Algorithmsforbichromatic

linesegmentproblemsandpolyhedralterrains”,Algorithmica,11(1994),pp.116–132.[8]H.Elgindy,M.Keil,“Efficientalgorithmsforthecapacitated1-medianproblem”,ORSAJ.

Comput,4(1982),pp.418–424.[9]F.Follert“LageoptimierungnachdemMaximin-Kriterium”,DiplomaThesis,Univ.d.Saar-landes,Saarbrucken,1984.[10]F.Follert,E.Sch¨omer,J.Sellen,“Subquadraticalgorithmsfortheweightedmaximinfacility

locationproblem”,inProc.7thCanad.Conf.Comput.Geom.,1-6,1995.[11]N.Megiddo,“Applyingparallelcomputationalgorithmsinthedesignofserialalgorithms”,

JournalofACM,30(1983),pp.852–865.[12]N.MegiddoandA.Tamir“Newresultsonthecomplexityofp-centerproblems”,SIAMJ.

Comput.,12(4),pp.751–758,1983.[13]K.Mehlhorn,“DataStructuresandAlgorithms3:Multi-dimensionalSearchingandCompu-tationalGeometry”,Springer-Verlag,1984.[14]F.Preparata“Newparallel-sortingschemes”,IEEETrans.Comput.,C-27,pp.669-673,1978.[15]D.E.Willard,G.S.Lueker,“Addingrangerestrictioncapabilitytodynamicdatastructures”,

inJ.ACM,32(1985),pp.597–617.

10