Query-Points Visibility Constraint Minimum Link Paths in Simple Polygons

• Autorzy: Zarrabi Mohammad Reza , Charkari Nasrollah Moghaddam

Identyfikatory

URI

10.3233/FI-2021-2075

• Języki publikacji: EN

Abstrakty

EN

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(n3) 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.

Słowa kluczowe

EN

Computational Geometry; Minimum Link Path; Shortest Path Map; Map Overlay

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 182, nr 3
• Strony: 301--319
• Opis fizyczny: Bibliogr. 18 poz., rys.

Twórcy

autor

Zarrabi Mohammad Reza

• Department of Electrical and Computer Engineering Tarbiat Modares University Tehran, Iran

autor

Charkari Nasrollah Moghaddam

• Department of Electrical and Computer Engineering Tarbiat Modares University Tehran, Iran

Bibliografia

• [1] Aggarwal A, Booth H, O’Rourke J, Suri S, Yap CK. Finding minimal convex nested polygons, Information and Computation, 1989. 83(1):98-110. doi:10.1016/0890-5401(89)90049-7.
• [2] Arkin EM, Mitchell JSB, Suri S. Logarithmic-time link path queries in a simple polygon, International Journal of Computational Geometry and Applications, 1995. 5(4):369-395. doi:10.1142/S0218195995000234.
• [3] Arkin EM, Efrat A, Knauer C, Mitchell JSB, Polishchuk V, Rote G, Schlipf L, Talvitie T. Shortest path to a segment and quickest visibility queries, Journal of Computational Geometry, 2016. 7(2):77-100. doi:10.4230/LIPIcs.SOCG.2015.658.
• [4] Chazelle B. Triangulating a simple polygon in linear time, Discrete and Computational Geometry, 1991. 6(3):485-524.
• [5] Chen DZ. Developing algorithms and software for geometric path planning problems, ACM Computing Surveys (CSUR), 1996. 28(4es):18-es. doi:10.1145/242224.242246.
• [6] Edelsbrunner H, Guibas LJ, Stolfi J. Optimal point location in a monotone subdivision, SIAM Journal on Computing, 1986. 15(2):317-340.
• [7] Finke U, Hinrichs KH. Overlaying simply connected planar subdivisions in linear time, In Proceedings of the eleventh annual symposium on Computational Geometry, ACM 1995:119-126. doi:10.1145/220279.220292.
• [8] Ghosh SK. Computing the visibility polygon from a convex set and related problems, Journal of Algorithms, 1991. 12(1):75-95. doi:10.1016/0196-6774(91)90024-S.
• [9] Guibas LJ, Hershberger J, Leven D, Sharir M, Tarjan RE. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons, Algorithmica, 1987. 2(1-4):209-233. doi:10.1007/BF01840360.
• [10] Guibas LJ, Hershberger J. Optimal shortest path queries in a simple polygon, Journal of Computer and System Sciences, 1989. 39(2):126-152. doi:10.1016/0022-0000(89)90041-X.
• [11] Hershberger J. An optimal visibility graph algorithm for triangulated simple polygons, Algorithmica, 1989. 4(1-4):141-155. doi:10.1007/BF01553883.
• [12] Khosravi R, Ghodsi M. The fastest way to view a query point in simple polygons, In Proceedings of the 21st European Workshop on Computational Geometry, 2005, pp. 187-190. ID: 2345696.
• [13] Khosravi R, Ghodsi M. Query-point visibility constrained shortest paths in simple polygons, Theoretical Computer Science, 2007. 389(1-2):1-11. doi:10.1016/j.tcs.2007.07.003.
• [14] Mitchell JSB, Rote G, Woeginger G. Minimum-link paths among obstacles in the plane, Algorithmica, 1992. 8(1-6):431-459. doi:10.1007/BF01758855.M.R. Zarrabi and N.M. Charkari / Query-Points Visibility Constraint Minimum Link Paths in Simple Polygons 319
• [15] Suri S. A linear time algorithm for minimum link path inside a simple polygon, Computer Vision, Graphics and Image Processing, 1986. 35(1):99-110.
• [16] Suri S. On some link distance problems in a simple polygon, IEEE transactions on Robotics and Automation, 1990. 6(1):108-113. doi:10.1109/70.88124.
• [17] Wang H. Quickest visibility queries in polygonal domains, Discrete and Computational Geometry, 2019. 62(2):374-432. doi:10.1007/s00454-019-00108-8.
• [18] Zarrabi MR, Charkari NM. Single-Point Visibility Constraint Minimum Link Paths in Simple Polygons, Submitted to Iranian Journal of Mathematical Sciences and Informatics, (Accepted 2019), arXiv preprint arXiv:2003.12778.

Uwagi

EN

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)