TY - JOUR
JF - IJMSI
JO - IJMSI
VL - 17
IS - 2
PY - 2022
Y1 - 2022/9/01
TI - Single-Point Visibility Constraint Minimum Link Paths in Simple Polygons
TT -
N2 - 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.
SP - 235
EP - 241
AU - Zarrabi, M. R.
AU - Moghadam Charkari, N.
AD - Faculty of Electrical Engineering and Computer Science, Tarbiat Modares University, Tehran, Iran
KW - Minimum link path
KW - Shortest path map
KW - Point location.
UR - http://ijmsi.ir/article-1-1436-en.html
DO - 10.52547/ijmsi.17.2.235
ER -