ﻻ يوجد ملخص باللغة العربية
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.
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)$
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
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 len
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
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 poly