论文标题
单点可见性约束最小链接路径
Single-Point Visibility Constraint Minimum Link Paths in Simple Polygons
论文作者
论文摘要
我们解决以下问题：给定一个简单的多边形$ p $，其中$ n $顶点以及其中的两个点$ s $和$ t $，找到它们之间的最小链接路径，以使给定的目标点$ q $从路径上的至少一个点可以看到。该方法基于将$ p $的一部分划分为距源点相等链路距离的许多面。该分区本质上是最短的路径图（SPM）。在本文中，我们提出了一种具有$ O（n）$时间绑定的最佳算法，该算法与标准最小链路路径问题的时间复杂性相同。
We address the following problem: Given a simple polygon $P$ with $n$ vertices and two points $s$ and $t$ inside it, find a minimum link path between them such that a given target point $q$ is visible from at least one point on the path. The method is based on partitioning a portion of $P$ into a number of faces of equal link distance from a source point. This partitioning is essentially a shortest path map (SPM). In this paper, we present an optimal algorithm with $O(n)$ time bound, which is the same as the time complexity of the standard minimum link paths problem.
