Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Divide-and-Conquer Algorithm for Two-Point $L_1$ Shortest Path Queries in Polygonal Domains
125
0
0.0
(
0
)
Added by
Haitao Wang
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Authors
Haitao Wang
Ask ChatGPT about the research
No Arabic abstract
Let $mathcal{P}$ be a polygonal domain of $h$ holes and $n$ vertices. We study the problem of constructing a data structure that can compute a shortest path between $s$ and $t$ in $mathcal{P}$ under the $L_1$ metric for any two query points $s$ and $t$. To do so, a standard approach is to first find a set of $n_s$ gateways for $s$ and a set of $n_t$ gateways for $t$ such that there exist a shortest $s$-$t$ path containing a gateway of $s$ and a gateway of $t$, and then compute a shortest $s$-$t$ path using these gateways. Previous algorithms all take quadratic $O(n_scdot n_t)$ time to solve this problem. In this paper, we propose a divide-and-conquer technique that solves the problem in $O(n_s + n_t log n_s)$ time. As a consequence, we construct a data structure of $O(n+(h^2log^3 h/loglog h))$ size in $O(n+(h^2log^4 h/loglog h))$ time such that each query can be answered in $O(log n)$ time.
rate research
Read More
For a polygonal domain with $h$ holes and a total of $n$ vertices, we present algorithms that compute the $L_1$ geodesic diameter in $O(n^2+h^4)$ time and the $L_1$ geodesic center in $O((n^4+n^2 h^4)alpha(n))$ time, respectively, where $alpha(cdot)$ denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in $O(n^{7.73})$ or $O(n^7(h+log n))$ time, and compute the geodesic center in $O(n^{11}log n)$ time. Therefore, our algorithms are significantly faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on $L_1$ shortest paths in polygonal domains.
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.
Given a set P of n points in the plane, a unit-disk graph G_{r}(P) with respect to a radius r is an undirected graph whose vertex set is P such that an edge connects two points p, q in P if the Euclidean distance between p and q is at most r. The length of any path in G_r(P) is the number of edges of the path. Given a value lambda>0 and two points s and t of P, we consider the following reverse shortest path problem: finding the smallest r such that the shortest path length between s and t in G_r(P) is at most lambda. It was known previously that the problem can be solved in O(n^{4/3} log^3 n) time. In this paper, we present an algorithm of O(lfloor lambda rfloor cdot n log n) time and another algorithm of O(n^{5/4} log^2 n) time.
Advantages in several fields of research and industry are expected with the rise of quantum computers. However, the computational cost to load classical data in quantum computers can impose restrictions on possible quantum speedups. Known algorithms to create arbitrary quantum states require quantum circuits with depth O(N) to load an N-dimensional vector. Here, we show that it is possible to load an N-dimensional vector with a quantum circuit with polylogarithmic depth and entangled information in ancillary qubits. Results show that we can efficiently load data in quantum devices using a divide-and-conquer strategy to exchange computational time for space. We demonstrate a proof of concept on a real quantum device and present two applications for quantum machine learning. We expect that this new loading strategy allows the quantum speedup of tasks that require to load a significant volume of information to quantum devices.
We consider the problem of finding minimum-link rectilinear paths in rectilinear polygonal domains in the plane. A path or a polygon is rectilinear if all its edges are axis-parallel. Given a set $mathcal{P}$ of $h$ pairwise-disjoint rectilinear polygonal obstacles with a total of $n$ vertices in the plane, a minimum-link rectilinear path between two points is a rectilinear path that avoids all obstacles with the minimum number of edges. In this paper, we present a new algorithm for finding minimum-link rectilinear paths among $mathcal{P}$. After the plane is triangulated, with respect to any source point $s$, our algorithm builds an $O(n)$-size data structure in $O(n+hlog h)$ time, such that given any query point $t$, the number of edges of a minimum-link rectilinear path from $s$ to $t$ can be computed in $O(log n)$ time and the actual path can be output in additional time linear in the number of the edges of the path. The previously best algorithm computes such a data structure in $O(nlog n)$ time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
