10.3233/FI-2021-2075 Zarrabi, Mohammad Reza Mohammad Reza Zarrabi Charkari, Nasrollah Moghaddam Nasrollah Moghaddam Charkari Query-points visibility constraint minimum link paths in simple polygons episciences.org 2021 Computer Science - Computational Geometry contact@episciences.org episciences.org 2021-08-24T11:44:26+02:00 2021-11-18T11:14:43+01:00 2021-11-18 eng Journal article https://fi.episciences.org/8386 arXiv:2004.02220 1875-8681 PDF 1 Fundamenta Informaticae ; Volume 182, Issue 3 ; 1875-8681 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.