We provide linear-time algorithms for geometric graphs with sublinearly many edge crossings. That is, we provide algorithms running in @math time on connected geometric graphs having @math vertices and @math pairwise crossings, where @math is smaller than @math by an iterated logarithmic factor. Specific problems that we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that “zeros in” on edge crossings, together with methods for applying planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having @math segments and @math crossings in linear time, for the case when @math is sublinear in @math by an iterated logarithmic factor.
In the algorithms community, there has been considerable prior work on shortest path algorithms for Euclidean graphs (e.g., see @cite_35 @cite_50 @cite_48 @cite_1 @cite_8 @cite_20 ), which are geometric graphs where edges are weighted by the lengths of the corresponding line segments. This prior work takes a decidedly different approach than we take in this paper, however, in that it focuses on using special properties of the edge weights that do not hold in the comparison model, whereas we study road networks as geometric graphs with a sublinear number of edge crossings and we desire linear-time algorithms that hold in the comparison model.
@cite_35 @cite_8 @cite_48 @cite_1 @cite_50 @cite_20
1989723858 2085630237 2056148792 2259676875
The problem of determining shortest paths through a weighted planar polygonal subdivision with n vertices is considered. Distances are measured according to a weighted Euclidean metric: The length of a path is defined to be the weighted sum of (Euclidean) lengths of the subpaths within each region. An algorithm that constructs a (restricted) “shortest path map” with respect to a given source point is presented. The output is a partitioning of each edge of the subdivion into intervals of e-optimality, allowing an e-optimal path to be traced from the source to any query point along any edge. The algorithm runs in worst-case time O ( ES ) and requires O ( E ) space, where E is the number of “events” in our algorithm and S is the time it takes to run a numerical search procedure. In the worst case, E is bounded above by O ( n 4 ) (and we give an O( n 4 ) lower bound), but it is likeky that E will be much smaller in practice. We also show that S is bounded by O ( n 4 L ), where L is the precision of the problem instance (including the number of bits in the user-specified tolerance e). Again, the value of S should be smaller in practice. The algorithm applies the “continuous Dijkstra” paradigm and exploits the fact that shortest paths obey Snell's Law of Refraction at region boundaries, a local optimaly property of shortest paths that is well known from the analogous optics model. The algorithm generalizes to the multi-source case to compute Voronoi diagrams. Shortest paths computations constitute one of the most fundamental network problems. Nonetheless, known parallel shortest-paths algorithms are generally inefficient: they perform significantly more work (product of time and processors) than their sequential counterparts. This gap, known in the literature as the “transitive closure bottleneck,” poses a long-standing open problem. Our main result is an O mn e 0 +s m+n1+ e 0 work polylog-time randomized algorithm that computes paths within (1 + O (1 polylog n ) of shortest from s source nodes to all other nodes in weighted undirected networks with n nodes and m edges (for any fixed e 0 >0). This work bound nearly matches the O d sm sequential time. In contrast, previous polylog-time algorithms required nearly min O d n3 , O d m2 work (even when s =1), and previous near-linear work algorithms required near- O ( n ) time. We also present faster sequential algorithms that provide good approximate distances only between “distant” vertices: We obtain an O m+sn n e 0 time algorithm that computes paths of weight (1+ O (1 polylog n ) dist + O ( w max polylog n ), where dist is the corresponding distance and w max is the maximum edge weight. Our chief instrument, which is of independent interest, are efficient constructions of sparse hop sets . A ( d ,e)-hop set of a network G =( V,E ) is a set E * of new weighted edges such that mimimum-weight d -edge paths in V,E∪E* have weight within (1+e) of the respective distances in G . We construct hop sets of size O n1+ e 0 where e= O (1 polylog n ) and d = O (polylog n ). We11A preliminary version appeared in the “Proceedings of the 2nd Israeli Symposium on the Theory of Computing and Systems, 1993.”consider parallel shortest-paths computations in weighted undirected graphsG=(V,E), wheren=|V| andm=|E|. The standardO(n3) work path-doubling (Floyd-Warshall) algorithm consists ofO(logn) phases, where in each phase, for every triplet of vertices (u1,u2,u3)?V3, the distance betweenu1andu3is updated to be no more than the sum of the previous-phase distances between u1,u2 and u2,u3 . We introduce a new NC algorithm that for ?=o(n), considers onlyO(n?2) triplets. Our algorithm performsO(n?2) work and augmentsEwithO(n?) new weighted edges such that between every pair of vertices, there exists a minimum weight path of size (number of edges)O(n ?) (whereO(f)?O(fpolylogn)). To compute shortest-paths, we apply to the augmented graph algorithms that are efficient for small-size shortest paths. We obtain anO(t) timeO(|S|n2+n3 t2) work deterministic PRAM algorithm for computing shortest-paths from |S| sources to all other vertices, wheret?nis a parameter. When the ratio of the largest edge weight and the smallest edge weight isnO(polylogn), the algorithm computes shortest paths. When weights are arbitrary, it computes paths within a factor of 1+n??(polylogn)of shortest. A prominent tool in many problems involving metric spaces is a notion of randomized low-diameter decomposition. Loosely speaking, ( )-decomposition refers to a probability distribution over partitions of the metric into sets of low diameter, such that nearby points (parameterized by ( >0 )) are likely to be “clustered” together. Applying this notion to the shortest-path metric in edge-weighted graphs, it is known that n-vertex graphs admit an (O( n) )-padded decomposition (Bartal, 37th annual symposium on foundations of computer science. IEEE, pp 184–193, 1996), and that excluded-minor graphs admit O(1)-padded decomposition (, 25th annual ACM symposium on theory of computing, pp 682–690, 1993; Fakcharoenphol and Talwar, J Comput Syst Sci 69(3), 485–497, 2004; , Proceedings of the 46th annual ACM symposium on theory of computing. STOC ’14, pp 79–88. ACM, New York, NY, USA, 2014). We design decompositions to the family of p-path-separable graphs, which was defined by Abraham and Gavoille (Proceedings of the twenty-fifth annual acm symposium on principles of distributed computing, PODC ’06, pp 188–197, 2006) and refers to graphs that admit vertex-separators consisting of at most p shortest paths in the graph. Our main result is that every p-path-separable n-vertex graph admits an (O( (p n)) )-decomposition, which refines the (O( n) ) bound for general graphs, and provides new bounds for families like bounded-treewidth graphs. Technically, our clustering process differs from previous ones by working in (the shortest-path metric of) carefully chosen subgraphs.