DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ahn H.-K | - |
dc.contributor.author | Peter Brass | - |
dc.contributor.author | Christian Knauer | - |
dc.contributor.author | Hyeon-Suk Na | - |
dc.contributor.author | Chan-Su Shin | - |
dc.date.accessioned | 2017-07-18T16:59:35Z | - |
dc.date.available | 2017-07-18T16:59:35Z | - |
dc.date.created | 2009-08-19 | - |
dc.date.issued | 2008-12 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | https://oasis.postech.ac.kr/handle/2014.oak/31099 | - |
dc.description.abstract | In this paper we study the problem of finding a set of k directions for a given simple polygon P, such that for each point p∈ ∈P there is at least one direction in which the line through p intersects the polygon only once. For k∈=∈1, this is the classical problem of finding directions in which the polygon is monotone, and all such directions can be found in linear time for a simple n-gon. For k∈>∈1, this problem becomes much harder; we give an O(n 5log2 n)-time algorithm for k∈=∈2, and O(n 3k∈+∈2)-time algorithm for k∈¥∈3. These results are the first on the generalization of the monotonicity problem. © 2008 Springer Berlin Heidelberg. | - |
dc.language | English | - |
dc.publisher | SPRINGER | - |
dc.relation.isPartOf | LECTURE NOTES ON COMPUTER SCIENCE | - |
dc.title | COVERING A SIMPLE POLYGON BY MONOTONE DIRECTIONS | - |
dc.type | Article | - |
dc.identifier.doi | 10.1007/978-3-540-92182-0_59 | - |
dc.type.rims | ART | - |
dc.identifier.bibliographicCitation | LECTURE NOTES ON COMPUTER SCIENCE, v.LNCS 5369, pp.668 - 679 | - |
dc.citation.endPage | 679 | - |
dc.citation.startPage | 668 | - |
dc.citation.title | LECTURE NOTES ON COMPUTER SCIENCE | - |
dc.citation.volume | LNCS 5369 | - |
dc.contributor.affiliatedAuthor | Ahn H.-K | - |
dc.identifier.scopusid | 2-s2.0-58549096763 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.isOpenAccess | N | - |
dc.type.docType | CONFERENCE PAPER | - |
dc.description.journalRegisteredClass | scopus | - |
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.