论文标题
查询点可见性约束最小链接路径
Query-points visibility constraint minimum link paths in simple polygons
论文作者
论文摘要
我们研究了一个简单的多边形$ p $与$ n $ dertices之间两个点之间约束的最小链路路径的查询版本，从而从查询点可以看到，路径上至少有一个点。该方法基于将$ p $划分为距链接距离的许多面，称为基于链接的最短路径映射（SPM）。最初，我们解决了两个给定点$ s $，$ t $和查询点$ q $的问题。然后，提议的解决方案将扩展到三个任意查询点$ s $，$ t $和$ q $的一般情况。在前者中，我们建议使用$ O（n）$预处理时间的算法。为后一种情况扩展了这种方法，我们开发了一种使用$ O（n^3）$预处理时间的算法。 $ q $ - $ - $可见的$路径的链接距离，$ s $，$ t $之间的路径以及时间$ o（\ log n）$和$ o（m+\ log n）$在上述两种情况下分别提供，其中$ m $是链接的数量。
We study the query version of constrained minimum link paths between two points inside a simple polygon $P$ with $n$ vertices such that there is at least one point on the path, visible from a query point. The method is based on partitioning $P$ into a number of faces of equal link distance from a point, called a link-based shortest path map (SPM). Initially, we solve this problem for two given points $s$, $t$ and a query point $q$. Then, the proposed solution is extended to a general case for three arbitrary query points $s$, $t$ and $q$. In the former, we propose an algorithm with $O(n)$ preprocessing time. Extending this approach for the latter case, we develop an algorithm with $O(n^3)$ preprocessing time. The link distance of a $q$-$visible$ path between $s$, $t$ as well as the path are provided in time $O(\log n)$ and $O(m+\log n)$, respectively, for the above two cases, where $m$ is the number of links.
