Approximate distance oracles for graphs with dense clusters

Approximate Distance Oracles for Graphs with Dense Clusters Mattias Andersson a, Joachim Gudmundsson b,1, Christos Levcopoulos a aDepartment of Computer Science, Lund University, Box 118, 221 00 Lund, Sweden. bDepartment of Mathematics and Computing Science, TU Eindhoven, 5600 MB, Eindhoven, the Netherlands. Abstract Let Gbe a graph containing Ndisjoint t-spanners that are inter-connected with Medges. We present an algorithm that constructs a data structure of size O(M2+nlog n) that answers (1 + ε)-approximate shortest path queries in Gin constant time, where nis the number of vertices of G. 1. Introduction The shortest-path (SP) problem for weighted graphs with nvertices and medges is a fundamental problem for which efficient solutions can now be found in any standard algorithms text, see also [6,8,12–14]. Lately the approximation version of this problem has also been studied extensively [1,5,7]. In numerous algorithms, the query version of the SP- problem frequently appears as a subroutine. In such a query, we are given two vertices and have to compute or approximate the shortest path between them. Thorup and Zwick [15] presented an algorithm for undirected weighted graphs that computes approximate solutions using a pre-computed data structure (the time of pre-processing was recently improved by Baswana and Sen [3]). Since the query time is essentially bounded by a constant, Thorup and Zwick refer to their queries as approximate distance oracles. We focus on the geometric version of this problem. A geometric graph G= (V,E) has vertices corresponding to points in Rdand edge weights from a Euclidean metric, and is said to be a t-spanner for V, if for any two points pand qin V, there exists a path of length at most ttimes the Euclidean distance between pand q. Again considerable pre- Email addresses: [email protected] (Mattias Andersson), [email protected] (Joachim Gudmundsson), [email protected] (Christos Levcopoulos). 1Supported by the Netherlands Organisation for Scientific Research (NWO) vious work exists on the shortest path and related problems for t-spanners. The geometric query version was recently studied by Gudmundsson et al. [9,10] and they presented the first data structure that answers approximate shortest-path queries in constant time, provided that the input graph is a t-spanner for some known constant t > 1. Their data structure uses O(nlog n) space and can be constructed in time O(mlog n). In this paper we extend this result to hold also for “islands” of t-spanners, i.e., a set of disjoint t-spanners G1,... ,GNinter-connected by Medges. We construct a data structure that can answer (1 + ε)-approximate shortest path queries in constant time. The data structure uses O(M2+nlog n) space and can be constructed in time O((m+M2) log n), hence for M=O(√n) the bound is essentially the same as in [9] and [10]. We claim that this generalization is natural in many applications. Consider for example the railway network in Europe where each country has a railway network which usually is a t-spanner for some small value t. The railway networks of the countries are then sparsely connected. Typically the number of inter-connecting edges is very small compared to the total number of edges in the network, see Fig. 1. In [9] it was shown that an approximate shortestpath distance oracle can be applied to a large number of problems, for example, finding shortest obstacle-avoiding path between two vertices in a planar polygonal domain with obstacles and interesting query versions of closest pair problems. The extension presented in this paper also generalises 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry (a) (b) Fig. 1. (a) Many geometric networks consists of a set of “dense” graphs that are sparsely connected.(b) Example of an instance where the dashed edges are inter-connecting edges. the results for the above mentioned problems. We will use the following notation. For points p and qin Rd,|pq|denotes the Euclidean distance between pand q. If Gis a geometric graph, then δG(p, q) denotes the Euclidean length of a shortest path in Gbetween pand q. If Pis a path in G between pand qhaving length ∆ with δG(p, q)≤ ∆≤(1+ε)·δG(p, q), then Pis a (1+ε)-approximate shortest path for pand q. The main result of this paper is stated in the following theorem: Theorem 1 Let Gbe a geometric graph, with n vertices and medges, consisting of a set of disjoint t-spanners G1=(V1,E1),... ,GN=(VN,EN) inter-connected by Medges, and let εbe a positive constant. One can construct a data structure in time O((m+M2) log n)using O(M2+nlog n) space that can answer (1 + ε)-approximate shortest path queries in constant time. The set of pairwise disjoint t-spanners G1= (V1,E1),... ,GN= (VN,EN) will be called the “islands” of Gand, an edge (u, v)∈ E is said to be an inter-connecting edge if u∈ Viand v∈ Vj, where i6=j. A vertex v∈ Viincident to an interconnecting edge is called an harbor and, the set of all harbors of Viis denoted Ci. Note that the total number of harbors is O(M) since the number of inter-connecting edges is M. 2. Tools In the construction of the distance oracle we will need several tools, among them the well-separated pair decomposition (WSPD) by Callahan and Kosaraju [4], a graph pruning tool by Gudmundsson et al. [9] and well-separated clusters by Krznaric and Levcopoulos [11]. Fig. 2. An example cell partition, with respect to V′, made by the algorithm. Doughnuts are drawn with solid lines, while inner cells are drawn with dotted ones. In this section, given a set Vof npoints in Rd, and a subset V′⊆ V, we show how to associate a representative point r∈ V to each point p∈ V, such that the distance |pr|+|rq|, for any point q∈ V′, is a good approximation of the distance |pq|. The total number of representative points is O(|V′|). The idea is to partition space into cells, such that all points included in a cell may share a common representative point. We will use the fact that, given a set Sof n points in Rd, an approximate nearest neighbor data structure can be efficiently computed (Mount et al. [2]). Next the algorithm for computing representative points is presented. As a pre-processing step we compute the b-cluster tree T([11]) of V′with b= 10/ε2. For a level iin Tlet ν(D1),... ,ν(Dℓi) be the nodes at that level, where D1,... ,Dℓiare the associated clusters. Let Dj,1. . . , Dj,ℓi+1 be the cluster associated with the children of ν(Dj). For each cluster Djpick an arbitrary vertex djas the center point of Dj. The set of the ℓicenter points is denoted D(i). Perform the following four steps for each level iof T. (i) Compute an approximate nearest neighbor structure with D(i) as input, as described by Mount et al. [2]. (ii) For each center point djin D(i) compute the (1 + ε)-approximate nearest neighbor of dj. The point returned by the structure is denoted vj. March 25-26, 2004 Seville (Spain) (iii) For each cluster Djconstruct two squares; is(Dj) and os(Dj) with centers at djand side length 2α= 2(1 + 1/ε)·rd(cl(Dj)) and 2β= 2ε|dj, vj|/(1 + ε) respectively, where α < β. The two squares are called the inner and outer shells of Dj, and the set theoretical difference between the inner and the outer shell is denoted the doughnut of Dj. (iv) The inner shell of Djis recursively partitioned into four equally sized squares, until each square seither (a) is completely included in S1≤k≤ℓi+1 os(Dj,k) (the union of the outer shells of the children of ν(Dj)). In this case the square is deleted and, hence, not further partitioned. Or, (b) has diameter at most ε 1+ε·K, where Kis the smallest distance between a point within sand a point in Dj. A (1 + ε)-approximation of Kcan be computed in time O(log |Dj|). This implies that the diameter of sis bounded by ε·K. The resulting cells are denoted inner cells. Note that, due to step 4a, every inner cell is empty of points from Dj. An illustration of the partition is shown in Fig. 2. Finally, after all levels of Thas been processed, we assign a representative point to each point pin V. Preprocess all the produced cells and perform a point-location query for each point. If pbelongs to a doughnut cell then the center point of the associated cluster (see step 1) is the representative point of p. Otherwise, if pbelongs to an inner cell Cand pis the first point within Cprocessed in this step then rep(C) is set to p. If pis not the first point then rep(p) = rep(C). Further, note that an inner cell may overlap with the union of the outer shells of the children of v(Dj). If a point is included in both an inner cell and an outer shell, we treat it as if it belonged to the inner cell, and assign a representative point as above. For the above algorithm we can show the following theorem: Theorem 2 Given a set Vof npoints in Rd, a subset V′⊆ V and a positive real value τ1<1, one can for each point p∈ V associate a representative point r(p)such that for any point h∈ V′, it holds that min{|p, r(p)|,|r(p), h|} ≤ τ1|p, h|. The number of representative points is O(|V′|)and they can be computed in time O(nlog n). 3. Constructing the Oracle In this section we consider the main result of the paper, Theorem 1. The section is divided into two subsections: first we present the construction of the structure and then how queries are answered. Note that the correctness analysis has been omitted. 3.1. Constructing the basic structures In this section we show how to pre-process G in time O((M2+m) log n) such that we obtain three structures that will help us answer (1 + ε)- approximate distance queries in constant time. We will assume that the number of edges in each subgraph is linear with respect to the number of vertices in Vi, if not the subgraph is pruned. This is done in time O(mlog n) [9]. Hence, we can from now on assume that #Ei=O(Vi). Let V′be the set of vertices in Vincident on an inter-connecting edge. Now we can apply Theorem 2 with parameters V,V′= Γ′and τ1to obtain a representative point for each point in V. Now we are ready to present the three structures: Oracle A: An oracle that given two points pand qanswers ‘yes’ if pand qbelongs to the same island, otherwise it will return the representative points (to be defined below) for pand q. Oracle B: An (1 + ε)-approximate distance oracle for any pair of points belonging to the same island. Matrix D: An O(M)× O(M) matrix. For each pair of representative points, pand q,Dcontains the (1 + ε)-approximate shortest distance between pand q. The representative point of a point pis denoted r(p), and the set of all representative points of Vi and Vis denoted Γiand Γ, respectively. Note that Ci⊆Γi. Now we turn our attention to the construction of the oracles and the matrix. The construction of Oracles Aand Bare rather straightforward, with construction details omitted. However, Oracle Acan be constructed in linear time, using linear space, and Oracle Bcan be constructed in O(mlog n) time, using O(nlog n) space. Matrix Dis constructed as follows. For each i, 1≤i≤N, compute the WSPD of Γiwith separation constant s= (1+τ2+τ3 τ3−τ2) (the constants τ2 and τ3are necessary for the correctness analy- 20th European Workshop on Computational Geometry p q Fig. 3. Illustrating the approximate shortest path between pand q. The boxes illustrate the “harbors” along the path. sis). As output we obtain a set of well-separated pairs {{(A1, B1},... ,{Awi, Bwi}}, such that wi= O(#Ci). Next, construct the non-Euclidean graph F= (Γ,E′) as follows. For each Γiand each wellseparated pair {Aj, Bj}of the WSPD of Γiselect two (arbitrary) representative points aj∈Ajand bj∈Bj. Add the edge (aj, bj) to E′with weight Bi(aj, bj), where Bi(p, q) denotes a call to oracle Bifor Giwith parameters pand q. Note that the graph Fwill have O(M) vertices and edges. Let Dbe an O(M)× O(M) matrix. For each representative point p∈Γ compute the singlesource shortest path in Fto every point qin Γ and store the distance of each path in D[p, q]. The total time for this step is O(M2log M), and it can be obtained by running Dijkstra’s algorithm M times. Lemma 3 The oracles Aand B, and the matrix Dcan be built in time O((M2+m) log n)and the total complexity of A,Band Mis O(M2+nlog n). 3.2. Answer a query Given the two oracles and the matrices presented above the query algorithm is very simple. Let r(p) denote the representative point of p∈ V. Now assume that we are given two points pand q. If pand qbelong to the same islands then we query Oracle B with input p, q and return the value obtained from the oracle. If pand qdoes not belong to the same island we return the sum of B(p, r(p)), D(r(p), r(q)) and B(r(q), q). Obviously this is done in constant time. Using Lemma 3 and analysing the correctness of the query algorithm above, we can finally show Theorem 1. References [1] D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28(4):1167–1181, 1999. [2] S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching. Journal of the ACM, 45(6):891-923, 1998. [3] S. Baswana and S. Sen. Approximate Distance Oracles for Unweighted Graphs in O(n2log n) Time. In Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, 2004. [4] P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to knearest-neighbors and n-body potential fields. Journal of the ACM, 42(1):67–90, 1995. [5] E. Cohen. Fast algorithms for constructing t-spanners and paths with stretch t.SIAM Journal on Computing, 28(1):210–236, 1998. [6] E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. In Numerische Mathmatik vol. 1, 1959. [7] D. Dor, S. Halperin, and U. Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740–1759, 2000. [8] M. L. Fredman, R. E. Tarjan Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596-615, 1987. [9] J. Gudmundsson, C. Levcopoulos, G. Narasimhan and M. Smid. Approximate Distance Oracles for Geometric graphs. In Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, 2002. [10] J. Gudmundsson, C. Levcopoulos, G. Narasimhan and M. Smid. Approximate Distance Oracles Revisited. In Proc. 13th International Symposium on Algorithms and Computation, 2002. [11] D. Krznaric and C. Levcopoulos. Computing hierarchies of clusters from the Euclidean minimum spanning tree in linear time. In Proc. 15th Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 1995. [12] R. Raman. Recent results on the single-source shortest paths problem. SIGACT News 28:81-87,1997. [13] M. Thorup. Floats, Integers, and Single Source Shortest Paths. Journal of Algorithms, 35(2):189-201, 2000. [14] M. Thorup Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time. Journal of the ACM, 46(3):362-394, 1999. [15] M. Thorup and U. Zwick. Approximate distance oracles. In Proc. 33rd ACM Symposium on Theory of Computing, 2001.