Mohammad Reza Zarrabi ; Nasrollah Moghaddam Charkari - Query-points visibility constraint minimum link paths in simple polygons

fi:8386 - Fundamenta Informaticae, November 18, 2021, Volume 182, Issue 3 - https://doi.org/10.3233/FI-2021-2075
Query-points visibility constraint minimum link paths in simple polygons

Authors: Mohammad Reza Zarrabi ; Nasrollah Moghaddam Charkari

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.


Volume: Volume 182, Issue 3
Published on: November 18, 2021
Accepted on: August 27, 2021
Submitted on: August 24, 2021
Keywords: Computer Science - Computational Geometry


Share

Consultation statistics

This page has been seen 22 times.
This article's PDF has been downloaded 4 times.