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 simple rectilinear polygon (i.e., @math ), then there always exists a rectilinear path that has both the minimum length and the minimum link distance for any two points @math and @math in @math @cite_22 @cite_28 . de Berg @cite_22 built a data structure of @math size in @math time that can find such a path in @math time for any two-point query. The preprocessing time and space were both reduced to @math by Schuierer @cite_25 (with @math query time).
@cite_28 @cite_25 @cite_22
2081751185 2118838969 2113370909
Let @math be a simple polygon of @math vertices. We consider two-point @math shortest path queries in @math . We build a data structure of @math size in @math time such that given any two query points @math and @math , the length of an @math shortest path from @math to @math in @math can be computed in @math time, or in @math time if both @math and @math are vertices of @math , and an actual shortest path can be output in additional linear time in the number of edges of the path. To achieve the result, we propose a mountain decomposition of simple polygons, which may be interesting in its own right. Most importantly, our approach is much simpler than the previous work on this problem. The problem of finding a minimum spanning tree connecting n points in a k-dimensional space is discussed under three common distance metrics -- Euclidean, rectilinear, and @math . By employing a subroutine that solves the post office problem, we show that, for fixed k @math 3, such a minimum spanning tree can be found in time O( @math ), where a(k) = @math . The bound can be improved to O( @math ) for points in the 3-dimensional Euclidean space. We also obtain o( @math ) algorithms for finding a farthest pair in a set of n points and for other related problems. Given a polygon @math , for two points @math and @math contained in the polygon, their is the length of the shortest @math -path within @math . A of radius @math centered at a point @math is the set of points in @math whose geodesic distance to @math is at most @math . We present a polynomial time @math -approximation algorithm for finding a densest geodesic unit disk packing in @math . Allowing arbitrary radii but constraining the number of disks to be @math , we present a @math -approximation algorithm for finding a packing in @math with @math geodesic disks whose minimum radius is maximized. We then turn our focus on of @math and present a @math -approximation algorithm for covering @math with @math geodesic disks whose maximal radius is minimized. Furthermore, we show that all these problems are @math -hard in polygons with holes. Lastly, we present a polynomial time exact algorithm which covers a polygon with two geodesic disks of minimum maximal radius. We consider distance queries in vertex-labeled planar graphs. For any fixed @math we show how to preprocess a directed planar graph with vertex labels and arc lengths into a data structure that answers queries of the following form. Given a vertex @math and a label @math return a @math -approximation of the distance from @math to its closest vertex with label @math . For a directed planar graph with @math vertices, such that the ratio of the largest to smallest arc length is bounded by @math , the preprocessing time is @math , the data structure size is @math , and the query time is @math . We also point out that a vertex label distance oracle for undirected planar graphs suggested in an earlier version of this paper is incorrect.