Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userShortest Paths Among Obstacles in the Plane Revisited
106
0
0.0
(
0
)
Added by
Haitao Wang
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Haitao Wang
Ask ChatGPT about the research
No Arabic abstract
Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. The previous best algorithm was given by Hershberger and Suri [FOCS 1993, SIAM J. Comput. 1999] and the algorithm runs in $O(nlog n)$ time and $O(nlog n)$ space, where $n$ is the total number of vertices of all obstacles. The algorithm is time-optimal because $Omega(nlog n)$ is a lower bound. It has been an open problem for over two decades whether the space can be reduced to $O(n)$. In this paper, we settle it by solving the problem in $O(nlog n)$ time and $O(n)$ space, which is optimal in both time and space; we achieve this by modifying the algorithm of Hershberger and Suri. Like their original algorithm, our new algorithm can build a shortest path map for a source point $s$ in $O(nlog n)$ time and $O(n)$ space, such that given any query point $t$, the length of a shortest path from $s$ to $t$ can be computed in $O(log n)$ time and a shortest path can be produced in additional time linear in the number of edges of the path.
rate research
Read More
This paper presents an optimal $Theta(n log n)$ algorithm for determining time-minimal rectilinear paths among $n$ transient rectilinear obstacles. An obstacle is transient if it exists in the scene only for a specific time interval, i.e., it appears and then disappears at specific times. Given a point robot moving with bounded speed among transient rectilinear obstacles and a pair of points $s$, $d$, we determine a time-minimal, obstacle-avoiding path from $s$ to $d$. The main challenge in solving this problem arises as the robot may be required to wait for an obstacle to disappear, before it can continue moving toward the destination. Our algorithm builds on the continuous Dijkstra paradigm, which simulates propagating a wavefront from the source point. We also solve a query version of this problem. For this, we build a planar subdivision with respect to a fixed source point, so that minimum arrival time to any query point can be reported in $O(log n)$ time, using point location for the query point in this subdivision.
Given a set of pairwise disjoint polygonal obstacles in the plane, finding an obstacle-avoiding Euclidean shortest path between two points is a classical problem in computational geometry and has been studied extensively. Previously, Hershberger and Suri [SIAM J. Comput. 1999] gave an algorithm of $O(nlog n)$ time and $O(nlog n)$ space, where $n$ is the total number of vertices of all obstacles. Recently, by modifying Hershberger and Suris algorithm, Wang [SODA 2021] reduced the space to $O(n)$ while the runtime of the algorithm is still $O(nlog n)$. In this paper, we present a new algorithm of $O(n+hlog h)$ time and $O(n)$ space, provided that a triangulation of the free space is given, where $h$ is the number of obstacles. The algorithm, which improves the previous work when $h=o(n)$, is optimal in both time and space as $Omega(n+hlog h)$ is a lower bound on the runtime. Our algorithm builds a shortest path map for a source point $s$, so that given any query point $t$, the shortest path length from $s$ to $t$ can be computed in $O(log n)$ time and a shortest $s$-$t$ path can be produced in additional time linear in the number of edges of the path.
We design fast deterministic algorithms for distance computation in the congested clique model. Our key contributions include: -- A $(2+epsilon)$-approximation for all-pairs shortest paths in $O(log^2{n} / epsilon)$ rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model. -- A $(1+epsilon)$-approximation for multi-source shortest paths from $O(sqrt{n})$ sources in $O(log^2{n} / epsilon)$ rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size. Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in $tilde{O}(n^{1/6})$ rounds.
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.
We consider the problem of computing shortest paths in weighted unit-disk graphs in constant dimension $d$. Although the single-source and all-pairs variants of this problem are well-studied in the plane case, no non-trivial exact distance oracles for unit-disk graphs have been known to date, even for $d=2$. The classical result of Sedgewick and Vitter [Algorithmica 86] shows that for weighted unit-disk graphs in the plane the $A^*$ search has average-case performance superior to that of a standard shortest path algorithm, e.g., Dijkstras algorithm. Specifically, if the $n$ corresponding points of a weighted unit-disk graph $G$ are picked from a unit square uniformly at random, and the connectivity radius is $rin (0,1)$, $A^*$ finds a shortest path in $G$ in $O(n)$ expected time when $r=Omega(sqrt{log n/n})$, even though $G$ has $Theta((nr)^2)$ edges in expectation. In other words, the work done by the algorithm is in expectation proportional to the number of vertices and not the number of edges. In this paper, we break this natural barrier and show even stronger sublinear time results. We propose a new heuristic approach to computing point-to-point exact shortest paths in unit-disk graphs. We analyze the average-case behavior of our heuristic using the same random graph model as used by Sedgewick and Vitter and prove it superior to $A^*$. Specifically, we show that, if we are able to report the set of all $k$ points of $G$ from an arbitrary rectangular region of the plane in $O(k + t(n))$ time, then a shortest path between arbitrary two points of such a random graph on the plane can be found in $O(1/r^2 + t(n))$ expected time. In particular, the state-of-the-art range reporting data structures imply a sublinear expected bound for all $r=Omega(sqrt{log n/n})$ and $O(sqrt{n})$ expected bound for $r=Omega(n^{-1/4})$ after only near-linear preprocessing of the point set.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
