{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,16]],"date-time":"2023-11-16T00:23:16Z","timestamp":1700094196804},"reference-count":18,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T00:00:00Z","timestamp":1643673600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,2,19]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1093\/comjnl\/bxab200","type":"journal-article","created":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T12:07:56Z","timestamp":1641038876000},"page":"496-507","source":"Crossref","is-referenced-by-count":0,"title":["Single-Point And Triple-Point Queries Visibility Constrained Minimum Link Paths In Simple Polygons"],"prefix":"10.1093","volume":"66","author":[{"given":"Mohammad","family":"Reza Zarrabi","sequence":"first","affiliation":[{"name":"Faculty of Electrical Engineering and Computer Science , Tarbiat Modares University, Tehran, Iran"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nasrollah","family":"Moghaddam Charkari","sequence":"additional","affiliation":[{"name":"Faculty of Electrical Engineering and Computer Science , Tarbiat Modares University, Tehran, Iran"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,2,1]]},"reference":[{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/0890-5401(89)90049-7","article-title":"Finding minimal convex nested polygons","volume":"83","author":"Aggarwal","year":"1989","journal-title":"Information and Computation"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1142\/S0218195995000234","article-title":"Logarithmic-time link path queries in a simple polygon","volume":"5","author":"Arkin","year":"1995","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"2023022013493049800_","first-page":"77","article-title":"Shortest path to a segment and quickest visibility queries","volume":"7","author":"Arkin","year":"2016","journal-title":"Journal of Computational Geometry"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/BF02574703","article-title":"Triangulating a simple polygon in linear time","volume":"6","author":"Chazelle","year":"1991","journal-title":"Discrete and Computational Geometry"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"18\u2013es","DOI":"10.1145\/242224.242246","article-title":"Developing algorithms and software for geometric path planning problems","volume":"28","author":"Chen","year":"1996","journal-title":"ACM Computing Surveys (CSUR)"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","article-title":"Optimal point location in a monotone subdivision","volume":"15","author":"Edelsbrunner","year":"1986","journal-title":"SIAM Journal on Computing"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1145\/220279.220292","volume-title":"Proceedings of the eleventh annual symposium on Computational Geometry","author":"Finke","year":"1995"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0196-6774(91)90024-S","article-title":"Computing the visibility polygon from a convex set and related problems","volume":"12","author":"Ghosh","year":"1991","journal-title":"Journal of Algorithms"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","article-title":"Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons","volume":"2","author":"Guibas","year":"1987","journal-title":"Algorithmica"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/0022-0000(89)90041-X","article-title":"Optimal shortest path queries in a simple polygon","volume":"39","author":"Guibas","year":"1989","journal-title":"Journal of Computer and System Sciences"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF01553883","article-title":"An optimal visibility graph algorithm for triangulated simple polygons","volume":"4","author":"Hershberger","year":"1989","journal-title":"Algorithmica"},{"key":"2023022013493049800_","first-page":"187","volume-title":"Proceedings of the 21st European Workshop on Computational Geometry","author":"Khosravi","year":"2005"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2007.07.003","article-title":"Query-point visibility constrained shortest paths in simple polygons","volume":"389","author":"Khosravi","year":"2007","journal-title":"Theoretical Computer Science"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/BF01758855","article-title":"Minimum-link paths among obstacles in the plane","volume":"8","author":"Mitchell","year":"1992","journal-title":"Algorithmica"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0734-189X(86)90127-1","article-title":"A linear time algorithm for minimum link path inside a simple polygon","volume":"35","author":"Suri","year":"1986","journal-title":"Computer Vision, Graphics and Image Processing"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1109\/70.88124","article-title":"On some link distance problems in a simple polygon","volume":"6","author":"Suri","year":"1990","journal-title":"IEEE transactions on Robotics and Automation"},{"key":"2023022013493049800_","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/s00454-019-00108-8","article-title":"Quickest visibility queries in polygonal domains","volume":"62","author":"Wang","year":"2019","journal-title":"Discrete and Computational Geometry"},{"key":"2023022013493049800_","first-page":"12778","article-title":"Single-Point Visibility Constraint Minimum Link Paths in Simple Polygons","author":"Zarrabi","year":"2019","journal-title":"Submitted to Iranian Journal of Mathematical Sciences and Informatics"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/2\/496\/49256519\/bxab200.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/2\/496\/49256519\/bxab200.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T04:26:11Z","timestamp":1700022371000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/2\/496\/6518261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,1]]},"references-count":18,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2,1]]},"published-print":{"date-parts":[[2023,2,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxab200","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,2]]},"published":{"date-parts":[[2022,2,1]]}}}