text: 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.
  @cite_7: 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.
  @cite_6: In this paper, we show that many graph search problems can be solved quite efficiently for a geometric intersection graph of horizontal and vertical line segments. We first extract several basic operations for depth first search and breadth first search on a graph. Then we present data structures for the intersection graph in terms of which those operations can be implemented in an efficient manner. The data structures enable us to solve various graph search problems besides depth first search and breadth first search. Specifying the results obtained in this paper for an intersection graph of n horizontal and vertical segments with m pairs of intersecting segments, we obtain algorithms with the following complexity, where @math . (i) Depth first search and breadth first search can be executed in @math time and @math space. (ii) The biconnected components can be found in @math time and @math space. (iii) A maximum matching and a maximum independent set can be found in $O...
  @cite_3: 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.
  @cite_24: 
  @cite_0: Recent advances on polygon triangulation have yielded efficient algorithms for a large number of problems dealing with a single simple polygon. If the input consists of several disjoint polygons, however, it is often desirable to merge them in preprocessing so as to produce a single polygon that retains the geometric characteristics of its individual components. We give an efficient method for doing so, which combines a generalized form of Jordan sorting with the efficient use of point location and interval trees. As a corollary, we are able to triangulate a collection of p disjoint Jordan polygonal chains in time O (n + p (log p)1+e), for any fixed e > 0, where n is the total number of vertices. A variant of the algorithm gives a running time of O ((n + p log p) log log p). The performance of these solutions approaches the lower bound of Ω (n + p log p).
  @cite_23: 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.
  @cite_12: 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.
summary: 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.