Given a rectilinear domain @math of @math pairwise-disjoint rectilinear obstacles with a total of @math vertices in the plane, we study the problem of computing bicriteria rectilinear shortest paths between two points @math and @math in @math . Three types of bicriteria rectilinear paths are considered: minimum-link shortest paths, shortest minimum-link paths, and minimum-cost paths where the cost of a path is a non-decreasing function of both the number of edges and the length of the path. The one-point and two-point path queries are also considered. Algorithms for these problems have been given previously. Our contributions are threefold. First, we find a critical error in all previous algorithms. Second, we correct the error in a not-so-trivial way. Third, we further improve the algorithms so that they are even faster than the previous (incorrect) algorithms when @math is relatively small. For example, for the minimum-link shortest paths, we obtain the following results. Our algorithm computes a minimum-link shortest @math - @math path in @math time. For the one-point queries, we build a data structure of size @math in @math time for a source point @math , such that given any query point @math , a minimum-link shortest @math - @math path can be determined in @math time. For the two-point queries, with @math time and space preprocessing, a minimum-link shortest @math - @math path can be determined in @math time for any two query points @math and @math ; alternatively, with @math time and @math space preprocessing, we can answer each two-point query in @math time.
If @math is a general rectilinear domain with @math , then there may not exist a rectilinear path that is both a minimum-link path and a shortest path @cite_23 . The problems of finding only minimum-link paths or only shortest paths have been studied extensively. Imai and Asano @cite_6 presented an @math time and space algorithm for finding a minimum-link path in @math , and the space was reduced to @math @cite_7 @cite_12 @cite_24 . Recently, @cite_3 proposed an @math time and @math space algorithm for the problem, after @math is triangulated (which can be done in @math time or @math time for any @math @cite_0 ). The algorithms in @cite_7 @cite_12 @cite_3 also construct an @math size data structure that can answer each one-point minimum-link path query in @math time.
@cite_7 @cite_6 @cite_3 @cite_24 @cite_0 @cite_23 @cite_12
2233662001 2113370909 2953216592 2118838969 1990187919 1985248597 1992176147 1989723858 1985010089 2166444590 2163030926 1782245179 2021380525 2886086760 2950552904 128419235 2952103668 2020449301 1979832172 2035228443
We present a new algorithm for finding minimum-link rectilinear paths among h rectilinear obstacles with a total of n vertices in the plane. After the plane is triangulated, for any point s, our algorithm builds an O(n)-size data structure in (O(n+h h) ) time, such that given any query point t, we can compute a minimum-link rectilinear path from s to t in (O( n+k) ) time, where k is the number of edges of the path, and the query time is (O( n) ) if we only want to know the value k. The previously best algorithm solves the problem in (O(n n) ) time. In this paper we study two link distance problems for rectilinear paths inside a simple rectilinear polygon P.First, we present a data structure using O(n log n) storage such that a shortest path between two query points can be computed efficiently. If both query points are vertices of P, the query time is O(1 + l), where l is the number of links. If the query points are arbitrary points inside P, then the query time becomes O(log n + l). The resulting path is not only optimal in the rectilinear link metric, but it is optimal in the L1-metric as well. Secondly, it is shown that the rectilinear link diameter of P can be computed in time O(n log n). We also give an approximation algorithm that runs in linear time. This algorithm produces a solution that differs by at most three links from the exact diameter.The solutions are based on a rectilinear version of Chazelle's polygon cutting theorem. This new theorem states that any simple rectilinear polygon can be cut into two rectilinear subpolygons of size at most 34 times the original size, and that such a cut segment can be found in linear time. Given @math wireless transceivers located in a plane, a fundamental problem in wireless communications is to construct a strongly connected digraph on them such that the constituent links can be scheduled in fewest possible time slots, assuming the SINR model of interference. In this paper, we provide an algorithm that connects an arbitrary point set in @math slots, improving on the previous best bound of @math due to Moscibroda. This is complemented with a super-constant lower bound on our approach to connectivity. An important feature is that the algorithms allow for bi-directional (half-duplex) communication. One implication of this result is an improved bound of @math on the worst-case capacity of wireless networks, matching the best bound known for the extensively studied average-case. We explore the utility of oblivious power assignments, and show that essentially all such assignments result in a worst case bound of @math slots for connectivity. This rules out a recent claim of a @math bound using oblivious power. On the other hand, using our result we show that @math slots suffice, where @math is the ratio between the largest and the smallest links in a minimum spanning tree of the points. Our results extend to the related problem of minimum latency aggregation scheduling, where we show that aggregation scheduling with @math latency is possible, improving upon the previous best known latency of @math . We also initiate the study of network design problems in the SINR model beyond strong connectivity, obtaining similar bounds for biconnected and @math -edge connected structures. We present a data structure that allows to preprocess a rectilinear polygon with n vertices such that, for any two query points, the shortest path in the rectilinear link or L1-metric can be reported in time O(log n+k) where k is the link length of the shortest path. If only the distance is of interest, the query time reduces to O(log n). Furthermore, if the query points are two vertices, the distance can be reported in time O(1) and a shortest path can be constructed in time O(1+k). The data structure can be computed in time O(n) and needs O(n) storage. As an application we present a linear time algorithm to compute the diameter of a simple rectilinear polygon w.r.t. the L1-metric. A path or a polygonal domain is C-oriented if the orientations of its edges belong to a set of C given orientations; this is a generalization of the notable rectilinear case ( C = 2 ). We study exact and approximation algorithms for minimum-link C-oriented paths and paths with unrestricted orientations, both in C-oriented and in general domains.Our two main algorithms are as follows:A subquadratic-time algorithm with a non-trivial approximation guarantee for general (unrestricted-orientation) minimum-link paths in general domains.An algorithm to find a minimum-link C-oriented path in a C-oriented domain. Our algorithm is simpler and more time-space efficient than the prior algorithm.We also obtain several related results:3SUM-hardness of determining the link distance with unrestricted orientations (even in a rectilinear domain).An optimal algorithm for finding a minimum-link rectilinear path in a rectilinear domain. The algorithm and its analysis are simpler than the existing ones.An extension of our methods to find a C-oriented minimum-link path in a general (not necessarily C-oriented) domain.A more efficient algorithm to compute a 2-approximate C-oriented minimum-link path.A notion of "robust" paths. We show how minimum-link C-oriented paths approximate the robust paths with unrestricted orientations to within an additive error of 1. The problem of processing shortest pa th queries in graphs arises in application areas such as intelligent t ranspor ta t ion system (ITS), geographic information system (GIS), and robotics. In this paper, we present an efficient algorithmic solution for processing shortest pa th queries in undirected planar graphs with non-negative edge weights. Previous algorithms for this problem on planar graphs all have a tradeoff between the query t ime and the da ta structure space used by the solutions. The previously best known trade-off on an n-vertex planar graph G in the worst case is O(v -r) t ime for a pa th length query and O(v -r + L) t ime for report ing an actual shortest path, with a da ta structure of O(n2 x ) space, where r is an integer parameter with 1 < r _< n and L is the number of edges on the output shortest path. We present a new scheme, called frame search, that exploits the graph planari ty in a novel fashion. Wi th this scheme, we build an improved da ta structure of O(n + pv -r + p2 r) space (in O(n + p2 v + pr 3 4) time), where p is the minimum cardinality of a face-covering of the planar embedding of G with 1 < p < O(n), and r is an integer parameter with 1 < r < p. This da ta structure enables us to process each length query in O(v -rlog r + a(n)) t ime and report an actual shortest path in an addit ional O(L) time, where a(n) is the inverse of Ackermann's function. In the worst case, our approach reduces the previously best query t ime by a factor of up to O(n 1 4) if the same amount of space is used. Our technique can also be applied to improve the previous query algorithms for some geometric shortest pa th problems on the plane. We study the problems of processing single-source and two-point shortest path queries among weighted polygonal obstacles in the rectilinear plane. For the single-source case, we construct a data structure in O(nlog3 2n) time and O(nlog n) space, where n is the number of obstacle vertices; this data structure enables us to report the length of a shortest path between the source and any query point in O(log n) time, and an actual shortest path in O(log n+ k) time, where k is the number of edges on the output path. For the two-point case, we construct a data structure in O(n2 log2n) time and space; this data structure enables us to report the length of a shortest path between two arbitrary query points in O(log2 n) time, and an actual shortest path in O(log2 n + k) time. Our work improves and generalizes the previously best-known results on computing rectilinear shortest paths among weighted polygonal obstacles. We also apply our techniques to processing two-point L1 shortest obstacle-avoiding path queries among arbitrary (i.e., not necessarily rectilinear) polygonal obstacles in the plane. No algorithm for processing two-point shortest path queries among weighted obstacles was previously known. 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. We present a practical algorithm for finding minimum-length paths between points in the Euclidean plane with (not necessarily convex) polygonal obstacles. Prior to this work, the best known algorithm for finding the shortest path between two points in the plane required O(n 2 log n) time and O (n 2 ) space, where n denotes the number of obstacle edges. Assuming that a triangulation or a Voronoi diagram for the obstacle space is provided with the input (if is not, either one can be precomputed in O ( n log n) time), we present an O(kn) time algorithm, where k denotes the number of “islands” (connected components) in the obstacle space. The algorithm uses only O(n) space and, given a source point s , produces an O(n) size data structure such that the distance between s and any other point x in the plane ( x ) is not necessarily an obstacle vertex or a point on an obstacle edge) can be computed in O (1) time. The algorithm can also be used to compute shortest paths for the movement of a disk (so that optimal movement for arbitrary objects can be computed to the accuracy of enclosing them with the smallest possible disk). Let @math be any undirected graph on @math vertices and @math edges. A path @math between any two vertices @math is said to be @math -approximate shortest path if its length is at most @math times the length of the shortest path between @math and @math . We consider the problem of building a compact data structure for a given graph @math which is capable of answering the following query for any @math and @math . report @math -approximate shortest path between @math and @math when vertex @math fails We present data structures for the single source as well all-pairs versions of this problem. Our data structures guarantee optimal query time. Most impressive feature of our data structures is that their size nearly match the size of their best static counterparts. We consider the problem of finding a rectilinear path between two designated points in the presence of rectilinear obstacles subject to various optimization functions in terms of the number of bends and the total length of the path. Specifically we are interested in finding a minimum bend shortest path, a shortest minimum bend path or a least-cost path where the cost is defined as a function of both the length and the number of bends of the path. We provide a unified approach by constructing a path-preserving graph. guaranteed to preserve all these three kinds of paths and give an O(K+e log e) algorithm to find them, where e is the total number of obstacle edges, and K is the number of intersections between tracks from extreme point and other tracks (defined in the text). K is bounded by O(et), where t is the number of extreme edges. In particular, if the obstacles are rectilinearly convex, then K is O(ne), where n is the number of obstacles. Extensions are made to find a shortest path with a bounded number of bends and a minimum-bend path with a bounded length. When a source point and obstacles are pre-given, queries for the assorted paths from the source to given points can be handled in O(log e+k) time after O(K+e log e) preprocessing, where k is the size of the goal path. The trans-dichotomous algorithm of Fredman and Willard8 and the running time for these problems are also discussed. We study the aggregate group nearest neighbor searching for the MAX operator in the plane. For a set @math of @math points and a query set @math of @math points, the query asks for a point of @math whose maximum distance to the points in @math is minimized. We present data structures for answering such queries for both @math and @math distance measures. Previously, only heuristic and approximation algorithms were given for both versions. For the @math version, we build a data structure of O(n) size in @math time, such that each query can be answered in @math time. For the @math version, we build a data structure in @math time and @math space, such that each query can be answered in @math time, and alternatively, we build a data structure in @math time and space for any @math , such that each query can be answered in @math time. Further, we extend our result for the @math version to the top- @math queries where each query asks for the @math points of @math whose maximum distances to @math are the smallest for any @math with @math : We build a data structure of O(n) size in @math time, such that each top- @math query can be answered in @math time. The rectilinear shortest path problem can be stated as follows: given a set of m non-intersecting simple polygonal obstacles in the plane, find a shortest L"1-metric (rectilinear) path from a point s to a point t that avoids all the obstacles. The path can touch an obstacle but does not cross it. This paper presents an algorithm with time complexity O(n+m(lgn)^3^ ^2), which is close to the known lower bound of @W(n+mlgm) for finding such a path. Here, n is the number of vertices of all the obstacles together. In this paper the shortest path and the minimum spanning tree problems in a graph with @math nodes and @math cost scenarios (objectives) are discussed. In order to choose a solution the min-max criterion is applied. The minmax versions of both problems are hard to approximate within @math for any @math . The best approximation algorithm for the min-max shortest path problem, known to date, has approximation ratio of @math . On the other hand, for the min-max spanning tree, there is a randomized algorithm with approximation ratio of @math . In this paper a deterministic @math -approximation algorithm for min-max shortest path is constructed. For min-max spanning tree a deterministic @math -approximation algorithm is proposed, which works for a large class of graphs and a randomized @math -approximation algorithm, which can be applied to all graphs, is constructed. It is also shown that the approximation ratios obtained are close to the integrality gaps of the corresponding LP relaxations. We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following: * Given a desired space allocation @math , we show how to construct in @math time a data structure of size @math that answers distance queries in @math time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever @math . * We provide a linear-space exact distance oracle for planar graphs with query time @math for any constant eps>0. This is the first such data structure with provable sublinear query time. * For edge lengths at least one, we provide an exact distance oracle of space @math such that for any pair of nodes at distance D the query time is @math . Comparable query performance had been observed experimentally but has never been explained theoretically. Our data structures are based on the following new tool: given a non-self-crossing cycle C with @math nodes, we can preprocess G in @math time to produce a data structure of size @math that can answer the following queries in @math time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA'05), which reports distances to the boundary of a face, rather than a cycle. The best distance oracles for planar graphs until the current work are due to Cabello (SODA'06), Djidjev (WG'96), and Fakcharoenphol and Rao (FOCS'01). For @math and space @math , we essentially improve the query time from @math to @math . Given n orthogonal line segments on the plane, their intersection graph is defined such that each vertex corresponds to a segment, and each edge corresponds to a pair of intersecting segments. Although this graph can have Θ(n2) edges, we show that breadth first search can be accomplished in O(nlogn) time and O(n) space. As an application, we show that the minimum link rectilinear path between two points s and t amidst rectilinear polygonal obstacles can be computed in O(nlogn) time and O(n) space, which is optimal. We mention other related results in the paper. The distributed single-source shortest paths problem is one of the most fundamental and central problems in the message-passing distributed computing. Classical Bellman-Ford algorithm solves it in @math time, where @math is the number of vertices in the input graph @math . Peleg and Rubinovich (FOCS'99) showed a lower bound of @math for this problem, where @math is the hop-diameter of @math . Whether or not this problem can be solved in @math time when @math is relatively small is a major notorious open question. Despite intensive research LP13,N14,HKN15,EN16,BKKL16 that yielded near-optimal algorithms for the approximate variant of this problem, no progress was reported for the original problem. In this paper we answer this question in the affirmative. We devise an algorithm that requires @math time, for @math , and @math time, for larger @math . This running time is sublinear in @math in almost the entire range of parameters, specifically, for @math . For the all-pairs shortest paths problem, our algorithm requires @math time, regardless of the value of @math . We also devise the first algorithm with non-trivial complexity guarantees for computing exact shortest paths in the multipass semi-streaming model of computation. From the technical viewpoint, our algorithm computes a hopset @math of a skeleton graph @math of @math without first computing @math itself. We then conduct a Bellman-Ford exploration in @math , while computing the required edges of @math on the fly. As a result, our algorithm computes exactly those edges of @math that it really needs, rather than computing approximately the entire @math . Given a set of nonintersecting polygonal obstacles in the plane, thelink distance between two pointss andt is the minimum number of edges required to form a polygonal path connectings tot that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in timeO(Eź(n) log2n) (and spaceO(E)), wheren is the total number of edges of the obstacles,E is the size of the visibility graph, and ź(n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted ats) of minimum-link paths froms to all obstacle vertices. This leads to a method of solving the query version of our problem (for query pointst). The problem of finding a rectilinear shortest path amongst obstacles may be stated as follows: Given a set of obstacles in the plane find a shortest rectilinear ( L 1 ) path from a point s to a point t which avoids all obstacles. The path may touch an obstacle but may not cross an obstacle. We study the rectilinear shortest path problem for the case where the obstacles are non-intersecting simple polygons, and present an O ( n (log n ) 2 ) algorithm for finding such a path, where n is the number of vertices of the obstacles. We also study the case of rectilinear obstacles in three dimensions, and show that L 1 shortest paths can be found in O ( n 2 (log n ) 3 ) time. Given an undirected graph @math , it is known that its edge-connectivity @math can be computed by solving @math max-flow problems. The best time bounds known for the problem are @math , due to Matula (28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 249–251) if G is simple, and @math , due to Even and Tarjan (SIAM J. Comput., 4 (1975), pp. 507–518) if G is multiple.An @math time algorithm for computing the edge-connectivity @math of a multigraph @math , where @math is the number of pairs of nodes between which G has an edge, is proposed. This algorithm does not use any max-flow algorithm but consists only of @math times of graph searches and edge contractions. This method is then extended to a capacitated network to compute its minimum cut capacity in @math time.