DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ahn, HK | - |
dc.contributor.author | Barba, L | - |
dc.contributor.author | Bose, P | - |
dc.contributor.author | De Carufel, JL | - |
dc.contributor.author | Korman, M | - |
dc.contributor.author | Oh, E | - |
dc.date.accessioned | 2017-07-19T13:20:51Z | - |
dc.date.available | 2017-07-19T13:20:51Z | - |
dc.date.created | 2017-01-24 | - |
dc.date.issued | 2016-12 | - |
dc.identifier.issn | 0179-5376 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/36860 | - |
dc.description.abstract | Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack et al. (Discrete Comput Geom 4(1): 611-626, 1989) showed an -time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved. In this paper we affirmatively answer this question and present a deterministic linear-time algorithm to solve this problem. | - |
dc.language | English | - |
dc.publisher | SPRINGER | - |
dc.relation.isPartOf | DISCRETE & COMPUTATIONAL GEOMETRY | - |
dc.title | A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon | - |
dc.type | Article | - |
dc.identifier.doi | 10.1007/S00454-016-9796-0 | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | DISCRETE & COMPUTATIONAL GEOMETRY, v.56, no.4, pp.836 - 859 | - |
dc.identifier.wosid | 000386504400002 | - |
dc.date.tcdate | 2019-02-01 | - |
dc.citation.endPage | 859 | - |
dc.citation.number | 4 | - |
dc.citation.startPage | 836 | - |
dc.citation.title | DISCRETE & COMPUTATIONAL GEOMETRY | - |
dc.citation.volume | 56 | - |
dc.contributor.affiliatedAuthor | Ahn, HK | - |
dc.contributor.affiliatedAuthor | Oh, E | - |
dc.identifier.scopusid | 2-s2.0-84978152357 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.wostc | 1 | - |
dc.description.scptc | 1 | * |
dc.date.scptcdate | 2018-05-121 | * |
dc.description.isOpenAccess | N | - |
dc.type.docType | Article | - |
dc.subject.keywordAuthor | Geodesic distance | - |
dc.subject.keywordAuthor | Facility location | - |
dc.subject.keywordAuthor | Simple polygons | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Theory & Methods | - |
dc.relation.journalWebOfScienceCategory | Mathematics | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
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.