2017/03/13 by Wang, Haitao
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1703.04466
Given a rectilinear domain P of h pairwise-disjoint rectilinear obstacles with a total of n vertices in the plane, we study the problem of computing bicriteria rectilinear shortest paths between two points s and t in P. 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 h is relatively small. For example, for the minimum-link shortest paths, we obtain the following results. Our algorithm computes a minimum-link shortest s-t path in O(n+hlog3/2 h) time. For the one-point queries, we build a data structure of size O(n+ hlog h) in O(n+hlog3/2 h) time for a source point s, such that given any query point t, a minimum-link shortest s-t path can be determined in O(log n) time. For the two-point queries, with O(n+h2log2 h) time and space preprocessing, a minimum-link shortest s-t path can be determined in O(log n+log2 h) time for any two query points s and t; alternatively, with O(n+h2⋅ log2 h ⋅ 4√(log h)) time and O(n+h2⋅ log h ⋅ 4√(log h)) space preprocessing, we can answer each two-point query in O(log n) time.