Let @math be a point in a polygonal domain @math of @math holes and @math vertices. We consider a quickest visibility query problem. Given a query point @math in @math , the goal is to find a shortest path in @math to move from @math to see @math as quickly as possible. Previously, (SoCG 2015) built a data structure of size @math that can answer each query in @math time, where @math is the inverse Ackermann function and @math is the size of the visibility polygon of @math in @math (and @math can be @math in the worst case). In this paper, we present a new data structure of size @math that can answer each query in @math time. Our result improves the previous work when @math is relatively small. In particular, if @math is a constant, then our result even matches the best result for the simple polygon case (i.e., @math ), which is optimal. As a by-product, we also have a new algorithm for a shortest-path-to-segment query problem. Given a query line segment @math in @math , the query seeks a shortest path from @math to all points of @math . Previously, gave a data structure of size @math that can answer each query in @math time, and another data structure of size @math with @math query time. We present a data structure of size @math with query time @math , which also favors small values of @math and is optimal when @math .
Similar in spirit to the point-to-segment'' shortest path problem, Cheung and Daescu @cite_28 considered a point-to-face'' shortest path problem in 3D and approximation algorithms were given for the problem.
@cite_28
1699564817 2170220350 1985010089 2058510050
We address the point-to-face approximate shortest path problem in R: Given a set of polyhedral obstacles with a total of n vertices, a source point s, an obstacle face f, and a real positive parameter epsilon, compute a path from s to f that avoids the interior of the obstacles and has length at most (1+epsilon) times the length of the shortest obstacle avoiding path from s to f. We present three approximation algorithms that take by extending three well-known "point-to-point" shortest path algorithms. We present new techniques for establishing lower bounds in robot motion planning problems. Our scheme is based on path encoding and uses homotopy equivalence classes of paths to encode state. We first apply the method to the shortest path problem in 3 dimensions. The problem is to find the shortest path under an Lp metric (e.g. a euclidean metric) between two points amid polyhedral obstacles. Although this problem has been extensively studied, there were no previously known lower bounds. We show that there may be exponentially many shortest path classes in single-source multiple-destination problems, and that the single-source single-destination problem is NP-hard. We use a similar proof technique to show that two dimensional dynamic motion planning with bounded velocity is NP-hard. Finally we extend the technique to compliant motion planning with uncertainty in control. Specifically, we consider a point in 3 dimensions which is commanded to move in a straight line, but whose actual motion may differ from the commanded motion, possibly involving sliding against obstacles. Given that the point initially lies in some start region, the problem of finding a sequence of commanded velocities which is guaranteed to move the point to the goal is shown to be non-deterministic exponential time hard, making it the first provably intractable problem in robotics. 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). We propose an optimal-time algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs in worst-case time O(n log n) and requires O(n log n) space, where n is the total number of vertices in the obstacle polygons. The algorithm is based on an efficient implementation of wavefront propagation among polygonal obstacles, and it actually computes a planar map encoding shortest paths from a fixed source point to all other points of the plane; the map can be used to answer single-source shortest path queries in O(log n) time. The time complexity of our algorithm is a significant improvement over all previously published results on the shortest path problem. Finally, we also discuss extensions to more general shortest path problems, involving nonpoint and multiple sources.