CSPTRQ is an interesting problem and its has attracted much attention. The CSPTRQ is a variant of the traditional PTRQ. As objects moving in a constrained-space are common, clearly, it can also find many applications. At the first sight, our problem
can be easily tackled by extending existing methods used to answer the PTRQ. Unfortunately, those classical techniques are not well suitable for our problem, due to a set of new challenges. We develop targeted solutions and demonstrate the efficiency and effectiveness of the proposed methods through extensive experiments.
In this article, we devise a concise algorithm for computing BOCP. Our method is simple, easy-to-implement but without loss of efficiency. Given two circular-arc polygons with $m$ and $n$ edges respectively, our method runs in $O(m+n+(l+k)log l)$ tim
e, using $O(m+n+k)$ space, where $k$ is the number of intersections, and $l$ is the number of {edge}s. Our algorithm has the power to approximate to linear complexity when $k$ and $l$ are small. The superiority of the proposed algorithm is also validated through empirical study.
Let $mathscr O$ be a set of $n$ disjoint obstacles in $mathbb{R}^2$, $mathscr M$ be a moving object. Let $s$ and $l$ denote the starting point and maximum path length of the moving object $mathscr M$, respectively. Given a point $p$ in ${R}^2$, we sa
y the point $p$ is achievable for $mathscr M$ such that $pi(s,p)leq l$, where $pi(cdot)$ denotes the shortest path length in the presence of obstacles. One is to find a region $mathscr R$ such that, for any point $pin mathbb{R}^2$, if it is achievable for $mathscr M$, then $pin mathscr R$; otherwise, $p otin mathscr R$. In this paper, we restrict our attention to the case of line-segment obstacles. To tackle this problem, we develop three algorithms. We first present a simpler-version algorithm for the sake of intuition. Its basic idea is to reduce our problem to computing the union of a set of circular visibility regions (CVRs). This algorithm takes $O(n^3)$ time. By analysing its dominant steps, we break through its bottleneck by using the short path map (SPM) technique to obtain those circles (unavailable beforehand), yielding an $O(n^2log n)$ algorithm. Owing to the finding above, the third algorithm also uses the SPM technique. It however, does not continue to construct the CVRs. Instead, it directly traverses each region of the SPM to trace the boundaries, the final algorithm obtains $O(nlog n)$ complexity.
This article proposes an PQR search method for probabilistic objects. The main idea of our method is to use a strategy called textit{pre-approximation} that can reduce the initial problem to a highly simplified version, implying that it makes the res
t of steps easy to tackle. In particular, this strategy itself is pretty simple and easy to implement. Furthermore, motivated by the cost analysis, we further optimize our solution. The optimizations are mainly based on two insights: (romannumeral 1) the number of textit{effective subdivision}s is no more than 1; and (romannumeral 2) an entity with the larger textit{span} is more likely to subdivide a single region. We demonstrate the effectiveness and efficiency of our proposed approaches through extensive experiments under various experimental settings.
