DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ahn, H.-K. | - |
dc.contributor.author | Oh, E. | - |
dc.contributor.author | Schlipf, L. | - |
dc.contributor.author | Stehn, F. | - |
dc.contributor.author | Strash, D. | - |
dc.date.accessioned | 2019-12-05T10:30:03Z | - |
dc.date.available | 2019-12-05T10:30:03Z | - |
dc.date.created | 2019-08-24 | - |
dc.date.issued | 2019-11 | - |
dc.identifier.issn | 0925-7721 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/100366 | - |
dc.description.abstract | We introduce a variant of the watchman route problem, which we call the quickest pair-visibility problem. Given two persons standing at points s and t in a simple polygon P with no holes, we want to minimize the distance they travel in order to see each other in P. We solve two variants of this problem, one minimizing the longer distance the two persons travel (min-max) and one minimizing the total travel distance (min-sum), optimally in linear time. We also consider a query version of this problem for the min-max variant. We can preprocess a simple n-gon in linear time so that the minimum of the longer distance the two persons travel can be computed in O(log(2) n) time for any two query positions s, t where the two persons start. (C) 2019 Elsevier B.V. All rights reserved. | - |
dc.language | English | - |
dc.publisher | ELSEVIER | - |
dc.relation.isPartOf | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | - |
dc.title | On Romeo and Juliet problems: Minimizing distance-to-sight | - |
dc.type | Article | - |
dc.identifier.doi | 10.1016/j.comgeo.2019.07.003 | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.84, pp.12 - 21 | - |
dc.identifier.wosid | 000488420300003 | - |
dc.citation.endPage | 21 | - |
dc.citation.startPage | 12 | - |
dc.citation.title | COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | - |
dc.citation.volume | 84 | - |
dc.contributor.affiliatedAuthor | Ahn, H.-K. | - |
dc.contributor.affiliatedAuthor | Oh, E. | - |
dc.identifier.scopusid | 2-s2.0-85069965926 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.isOpenAccess | N | - |
dc.type.docType | Article | - |
dc.subject.keywordPlus | Applications | - |
dc.subject.keywordPlus | Computational geometry | - |
dc.subject.keywordPlus | Linear time | - |
dc.subject.keywordPlus | Min-sum | - |
dc.subject.keywordPlus | Preprocess | - |
dc.subject.keywordPlus | Shortest path | - |
dc.subject.keywordPlus | Simple polygon | - |
dc.subject.keywordPlus | Travel distance | - |
dc.subject.keywordPlus | Watchman problems | - |
dc.subject.keywordPlus | Watchman Route Problem | - |
dc.subject.keywordPlus | Visibility | - |
dc.subject.keywordAuthor | Shortest path | - |
dc.subject.keywordAuthor | Visibility polygon | - |
dc.subject.keywordAuthor | Watchman problems | - |
dc.relation.journalWebOfScienceCategory | Mathematics, Applied | - |
dc.relation.journalWebOfScienceCategory | Mathematics | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Mathematics | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
library@postech.ac.kr Tel: 054-279-2548
Copyrights © by 2017 Pohang University of Science ad Technology All right reserved.