Single-Point And Triple-Point Queries Visibility Constrained Minimum Link Paths In Simple Polygons. (1st February 2022) - Reza Zarrabi, Mohammad; Moghaddam Charkari, Nasrollah
Abstract: 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. This partitioning is essentially a link-based shortest path map. 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 case, we propose an algorithm with O(n) preprocessing time. 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 and the path are provided in time O(n) and O(m+n), respectively, for the above two cases, where m is the number of links.