Single-Point And Triple-Point Queries Visibility Constrained Minimum Link Paths In Simple Polygons. (1st February 2022)

• Record Type: Journal Article
• Authors: Reza Zarrabi, Mohammad; Moghaddam Charkari, Nasrollah
• Is Part Of: Computer journal. Volume 66:Number 2(2023)
• Page Start: 496
• Page End: 507
• Publication Date: 2022-02-01
• Subjects: Computational Geometry -- Minimum Link Path -- Shortest Path Map -- Map Overlay; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab200
• Languages: English
• ISSNs: 0010-4620

Abstract

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(\log n)$ and $O(m+\log n)$, respectively, for the above two cases, where $m$ is the number of links.