Approximate distance oracles for graphs with dense clusters

App oxima e Dis ance O acles o G aphs wi h Dense Clus e s Ma ias Ande sson a, Joachim Gudmundsson b,1, Ch is os Le copoulos a aDepa men o Compu e Science, Lund Uni e si y, Box 118, 221 00 Lund, Sweden. bDepa men o Ma hema ics and Compu ing Science, TU Eindho en, 5600 MB, Eindho en, he Ne he lands. Abs ac Le Gbe a g aph con aining Ndisjoin -spanne s ha a e in e -connec ed wi h Medges. We p esen an algo i hm ha cons uc s a da a s uc u e o size O(M2+nlog n) ha answe s (1 + ε)-app oxima e sho es pa h que ies in Gin cons an ime, whe e nis he numbe o e ices o G. 1. In oduc ion The sho es -pa h (SP) p oblem o weigh ed g aphs wi h n e ices and medges is a unda- men al p oblem o which e icien solu ions can now be ound in any s anda d algo i hms ex , see also [6,8,12–14]. La ely he app oxima ion e sion o his p ob- lem has also been s udied ex ensi ely [1,5,7]. In nume ous algo i hms, he que y e sion o he SP- p oblem equen ly appea s as a sub ou ine. In such a que y, we a e gi en wo e ices and ha e o compu e o app oxima e he sho es pa h be ween hem. Tho up and Zwick [15] p esen ed an algo- i hm o undi ec ed weigh ed g aphs ha com- pu es app oxima e solu ions using a p e-compu ed da a s uc u e ( he ime o p e-p ocessing was e- cen ly imp o ed by Baswana and Sen [3]). Since he que y ime is essen ially bounded by a con- s an , Tho up and Zwick e e o hei que ies as app oxima e dis ance o acles. We ocus on he geome ic e sion o his p ob- lem. A geome ic g aph G= (V,E) has e ices co - esponding o poin s in Rdand edge weigh s om a Euclidean me ic, and is said o be a -spanne o V, i o any wo poin s pand qin V, he e ex- is s a pa h o leng h a mos imes he Euclidean dis ance be ween pand q. Again conside able p e- Email add esses: ma [email protected] h.se (Ma ias Ande sson), h.j.gudmundsson@ ue.nl (Joachim Gudmundsson), ch is [email protected] h.se (Ch is os Le copoulos). 1Suppo ed by he Ne he lands O ganisa ion o Scien i ic Resea ch (NWO) ious wo k exis s on he sho es pa h and ela ed p oblems o -spanne s. The geome ic que y e - sion was ecen ly s udied by Gudmundsson e al. [9,10] and hey p esen ed he i s da a s uc u e ha answe s app oxima e sho es -pa h que ies in cons an ime, p o ided ha he inpu g aph is a -spanne o some known cons an > 1. Thei da a s uc u e uses O(nlog n) space and can be cons uc ed in ime O(mlog n). In his pape we ex end his esul o hold also o “islands” o -spanne s, i.e., a se o dis- join -spanne s G1,... ,GNin e -connec ed by Medges. We cons uc a da a s uc u e ha can answe (1 + ε)-app oxima e sho es pa h que ies in cons an ime. The da a s uc u e uses O(M2+nlog n) space and can be cons uc ed in ime O((m+M2) log n), hence o M=O(√n) he bound is essen ially he same as in [9] and [10]. We claim ha his gene aliza ion is na u al in many applica ions. Conside o example he ail- way ne wo k in Eu ope whe e each coun y has a ailway ne wo k which usually is a -spanne o some small alue . The ailway ne wo ks o he coun ies a e hen spa sely connec ed. Typically he numbe o in e -connec ing edges is e y small compa ed o he o al numbe o edges in he ne - wo k, see Fig. 1. In [9] i was shown ha an app oxima e sho es - pa h dis ance o acle can be applied o a la ge numbe o p oblems, o example, inding sho es obs acle-a oiding pa h be ween wo e ices in a plana polygonal domain wi h obs acles and in e - es ing que y e sions o closes pai p oblems. The ex ension p esen ed in his pape also gene alises 20 h EWCG Se ille, Spain (2004) 20 h Eu opean Wo kshop on Compu a ional Geome y (a) (b) Fig. 1. (a) Many geome ic ne wo ks consis s o a se o “dense” g aphs ha a e spa sely connec ed.(b) Example o an ins ance whe e he dashed edges a e in e -connec ing edges. he esul s o he abo e men ioned p oblems. We will use he ollowing no a ion. Fo poin s p and qin Rd,|pq|deno es he Euclidean dis ance be ween pand q. I Gis a geome ic g aph, hen δG(p, q) deno es he Euclidean leng h o a sho es pa h in Gbe ween pand q. I Pis a pa h in G be ween pand qha ing leng h ∆ wi h δG(p, q)≤ ∆≤(1+ε)·δG(p, q), hen Pis a (1+ε)-app oxima e sho es pa h o pand q. The main esul o his pape is s a ed in he ollowing heo em: Theo em 1 Le Gbe a geome ic g aph, wi h n e ices and medges, consis ing o a se o dis- join -spanne s G1=(V1,E1),... ,GN=(VN,EN) in e -connec ed by Medges, and le εbe a posi i e cons an . One can cons uc a da a s uc u e in ime O((m+M2) log n)using O(M2+nlog n) space ha can answe (1 + ε)-app oxima e sho es pa h que ies in cons an ime. The se o pai wise disjoin -spanne s G1= (V1,E1),... ,GN= (VN,EN) will be called he “islands” o Gand, an edge (u, )∈ E is said o be an in e -connec ing edge i u∈ Viand ∈ Vj, whe e i6=j. A e ex ∈ Viinciden o an in e - connec ing edge is called an ha bo and, he se o all ha bo s o Viis deno ed Ci. No e ha he o al numbe o ha bo s is O(M) since he numbe o in e -connec ing edges is M. 2. Tools In he cons uc ion o he dis ance o acle we will need se e al ools, among hem he well-sepa a ed pai decomposi ion (WSPD) by Callahan and Kosa aju [4], a g aph p uning ool by Gudmunds- son e al. [9] and well-sepa a ed clus e s by K z- na ic and Le copoulos [11]. Fig. 2. An example cell pa i ion, wi h espec o V′, made by he algo i hm. Doughnu s a e d awn wi h solid lines, while inne cells a e d awn wi h do ed ones. In his sec ion, gi en a se Vo npoin s in Rd, and a subse V′⊆ V, we show how o associa e a ep esen a i e poin ∈ V o each poin p∈ V, such ha he dis ance |p |+| q|, o any poin q∈ V′, is a good app oxima ion o he dis ance |pq|. The o al numbe o ep esen a i e poin s is O(|V′|). The idea is o pa i ion space in o cells, such ha all poin s included in a cell may sha e a common ep esen a i e poin . We will use he ac ha , gi en a se So n poin s in Rd, an app oxima e nea es neighbo da a s uc u e can be e icien ly compu ed (Moun e al. [2]). Nex he algo i hm o compu ing ep esen a- i e poin s is p esen ed. As a p e-p ocessing s ep we compu e he b-clus e ee T([11]) o V′wi h b= 10/ε2. Fo a le el iin Tle ν(D1),... ,ν(Dℓi) be he nodes a ha le el, whe e D1,... ,Dℓia e he associa ed clus e s. Le Dj,1. . . , Dj,ℓi+1 be he clus e associa ed wi h he child en o ν(Dj). Fo each clus e Djpick an a bi a y e ex djas he cen e poin o Dj. The se o he ℓicen e poin s is deno ed D(i). Pe o m he ollowing ou s eps o each le el io T. (i) Compu e an app oxima e nea es neighbo s uc u e wi h D(i) as inpu , as desc ibed by Moun e al. [2]. (ii) Fo each cen e poin djin D(i) compu e he (1 + ε)-app oxima e nea es neighbo o dj. The poin e u ned by he s uc u e is de- no ed j. Ma ch 25-26, 2004 Se ille (Spain) (iii) Fo each clus e Djcons uc wo squa es; is(Dj) and os(Dj) wi h cen e s a djand side leng h 2α= 2(1 + 1/ε)· d(cl(Dj)) and 2β= 2ε|dj, j|/(1 + ε) espec i ely, whe e α < β. The wo squa es a e called he inne and ou e shells o Dj, and he se heo e ical di e ence be ween he inne and he ou e shell is deno ed he doughnu o Dj. (i ) The inne shell o Djis ecu si ely pa i- ioned in o ou equally sized squa es, un- il each squa e sei he (a) is comple ely in- cluded in S1≤k≤ℓi+1 os(Dj,k) ( he union o he ou e shells o he child en o ν(Dj)). In his case he squa e is dele ed and, hence, no u he pa i ioned. O , (b) has diame e a mos ε 1+ε·K, whe e Kis he smalles dis- ance be ween a poin wi hin sand a poin in Dj. A (1 + ε)-app oxima ion o Kcan be compu ed in ime O(log |Dj|). This implies ha he diame e o sis bounded by ε·K. The esul ing cells a e deno ed inne cells. No e ha , due o s ep 4a, e e y inne cell is emp y o poin s om Dj. An illus a ion o he pa i ion is shown in Fig. 2. Finally, a e all le els o Thas been p ocessed, we assign a ep esen a i e poin o each poin pin V. P ep ocess all he p oduced cells and pe o m a poin -loca ion que y o each poin . I pbelongs o a doughnu cell hen he cen e poin o he associa ed clus e (see s ep 1) is he ep esen a i e poin o p. O he wise, i pbelongs o an inne cell Cand pis he i s poin wi hin Cp ocessed in his s ep hen ep(C) is se o p. I pis no he i s poin hen ep(p) = ep(C). Fu he , no e ha an inne cell may o e lap wi h he union o he ou e shells o he child en o (Dj). I a poin is included in bo h an inne cell and an ou e shell, we ea i as i i belonged o he inne cell, and assign a ep esen a i e poin as abo e. Fo he abo e algo i hm we can show he ol- lowing heo em: Theo em 2 Gi en a se Vo npoin s in Rd, a subse V′⊆ V and a posi i e eal alue τ1<1, one can o each poin p∈ V associa e a ep esen a i e poin (p)such ha o any poin h∈ V′, i holds ha min{|p, (p)|,| (p), h|} ≤ τ1|p, h|. The numbe o ep esen a i e poin s is O(|V′|)and hey can be compu ed in ime O(nlog n). 3. Cons uc ing he O acle In his sec ion we conside he main esul o he pape , Theo em 1. The sec ion is di ided in o wo subsec ions: i s we p esen he cons uc ion o he s uc u e and hen how que ies a e answe ed. No e ha he co ec ness analysis has been omi ed. 3.1. Cons uc ing he basic s uc u es In his sec ion we show how o p e-p ocess G in ime O((M2+m) log n) such ha we ob ain h ee s uc u es ha will help us answe (1 + ε)- app oxima e dis ance que ies in cons an ime. We will assume ha he numbe o edges in each sub- g aph is linea wi h espec o he numbe o e - ices in Vi, i no he subg aph is p uned. This is done in ime O(mlog n) [9]. Hence, we can om now on assume ha #Ei=O(Vi). Le V′be he se o e ices in Vinciden on an in e -connec ing edge. Now we can apply Theo- em 2 wi h pa ame e s V,V′= Γ′and τ1 o ob ain a ep esen a i e poin o each poin in V. Now we a e eady o p esen he h ee s uc u es: O acle A: An o acle ha gi en wo poin s pand qanswe s ‘yes’ i pand qbelongs o he same island, o he wise i will e u n he ep esen a i e poin s ( o be de ined below) o pand q. O acle B: An (1 + ε)-app oxima e dis ance o a- cle o any pai o poin s belonging o he same island. Ma ix D: An O(M)× O(M) ma ix. Fo each pai o ep esen a i e poin s, pand q,Dcon- ains he (1 + ε)-app oxima e sho es dis ance be ween pand q. The ep esen a i e poin o a poin pis deno ed (p), and he se o all ep esen a i e poin s o Vi and Vis deno ed Γiand Γ, espec i ely. No e ha Ci⊆Γi. Now we u n ou a en ion o he con- s uc ion o he o acles and he ma ix. The cons uc ion o O acles Aand Ba e a he s aigh o wa d, wi h cons uc ion de ails omi - ed. Howe e , O acle Acan be cons uc ed in lin- ea ime, using linea space, and O acle Bcan be cons uc ed in O(mlog n) ime, using O(nlog n) space. Ma ix Dis cons uc ed as ollows. Fo each i, 1≤i≤N, compu e he WSPD o Γiwi h sep- a a ion cons an s= (1+τ2+τ3 τ3−τ2) ( he cons an s τ2 and τ3a e necessa y o he co ec ness analy- 20 h Eu opean Wo kshop on Compu a ional Geome y p q Fig. 3. Illus a ing he app oxima e sho es pa h be ween pand q. The boxes illus a e he “ha bo s” along he pa h. sis). As ou pu we ob ain a se o well-sepa a ed pai s {{(A1, B1},... ,{Awi, Bwi}}, such ha wi= O(#Ci). Nex , cons uc he non-Euclidean g aph F= (Γ,E′) as ollows. Fo each Γiand each well- sepa a ed pai {Aj, Bj}o he WSPD o Γiselec wo (a bi a y) ep esen a i e poin s aj∈Ajand bj∈Bj. Add he edge (aj, bj) o E′wi h weigh Bi(aj, bj), whe e Bi(p, q) deno es a call o o acle Bi o Giwi h pa ame e s pand q. No e ha he g aph Fwill ha e O(M) e ices and edges. Le Dbe an O(M)× O(M) ma ix. Fo each ep esen a i e poin p∈Γ compu e he single- sou ce sho es pa h in F o e e y poin qin Γ and s o e he dis ance o each pa h in D[p, q]. The o al ime o his s ep is O(M2log M), and i can be ob ained by unning Dijks a’s algo i hm M imes. Lemma 3 The o acles Aand B, and he ma ix Dcan be buil in ime O((M2+m) log n)and he o al complexi y o A,Band Mis O(M2+nlog n). 3.2. Answe a que y Gi en he wo o acles and he ma ices p e- sen ed abo e he que y algo i hm is e y simple. Le (p) deno e he ep esen a i e poin o p∈ V. Now assume ha we a e gi en wo poin s pand q. I pand qbelong o he same islands hen we que y O acle B wi h inpu p, q and e u n he alue ob ained om he o acle. I pand qdoes no belong o he same island we e u n he sum o B(p, (p)), D( (p), (q)) and B( (q), q). Ob i- ously his is done in cons an ime. Using Lemma 3 and analysing he co ec ness o he que y algo i hm abo e, we can inally show Theo em 1. Re e ences [1] D. Aingwo h, C. Cheku i, P. Indyk, and R. Mo wani. Fas es ima ion o diame e and sho es pa hs (wi hou ma ix mul iplica ion). SIAM Jou nal on Compu ing, 28(4):1167–1181, 1999. [2] S. A ya, D. M. Moun , N. S. Ne anyahu, R. Sil e man, and A. Y. Wu. An op imal algo i hm o app oxima e nea es neighbo sea ching. Jou nal o he ACM, 45(6):891-923, 1998. [3] S. Baswana and S. Sen. App oxima e Dis ance O acles o Unweigh ed G aphs in O(n2log n) Time. In P oc. 15 h Annual ACM-SIAM Symposium on Disc e e Algo i hms, 2004. [4] P. B. Callahan and S. R. Kosa aju. A decomposi ion o mul idimensional poin se s wi h applica ions o k- nea es -neighbo s and n-body po en ial ields. Jou nal o he ACM, 42(1):67–90, 1995. [5] E. Cohen. Fas algo i hms o cons uc ing -spanne s and pa hs wi h s e ch .SIAM Jou nal on Compu ing, 28(1):210–236, 1998. [6] E. W. Dijks a. A No e on Two P oblems in Connexion wi h G aphs. In Nume ische Ma hma ik ol. 1, 1959. [7] D. Do , S. Halpe in, and U. Zwick. All-pai s almos sho es pa hs. SIAM Jou nal on Compu ing, 29(5):1740–1759, 2000. [8] M. L. F edman, R. E. Ta jan Fibonacci heaps and hei uses in imp o ed ne wo k op imiza ion algo i hms. Jou nal o he ACM, 34(3):596-615, 1987. [9] J. Gudmundsson, C. Le copoulos, G. Na asimhan and M. Smid. App oxima e Dis ance O acles o Geome ic g aphs. In P oc. 13 h ACM-SIAM Symposium on Disc e e Algo i hms, 2002. [10] J. Gudmundsson, C. Le copoulos, G. Na asimhan and M. Smid. App oxima e Dis ance O acles Re isi ed. In P oc. 13 h In e na ional Symposium on Algo i hms and Compu a ion, 2002. [11] D. K zna ic and C. Le copoulos. Compu ing hie a chies o clus e s om he Euclidean minimum spanning ee in linea ime. In P oc. 15 h Annual Con e ence on Founda ions o So wa e Technology and Theo e ical Compu e Science, 1995. [12] R. Raman. Recen esul s on he single-sou ce sho es pa hs p oblem. SIGACT News 28:81-87,1997. [13] M. Tho up. Floa s, In ege s, and Single Sou ce Sho es Pa hs. Jou nal o Algo i hms, 35(2):189-201, 2000. [14] M. Tho up Undi ec ed Single-Sou ce Sho es Pa hs wi h Posi i e In ege Weigh s in Linea Time. Jou nal o he ACM, 46(3):362-394, 1999. [15] M. Tho up and U. Zwick. App oxima e dis ance o acles. In P oc. 33 d ACM Symposium on Theo y o Compu ing, 2001.