COVERING A SIMPLE POLYGON BY MONOTONE DIRECTIONS
SCOPUS
- Title
- COVERING A SIMPLE POLYGON BY MONOTONE DIRECTIONS
- Authors
- Ahn H.-K; Peter Brass; Christian Knauer; Hyeon-Suk Na; Chan-Su Shin
- Date Issued
- 2008-12
- Publisher
- SPRINGER
- 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.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/31099
- DOI
- 10.1007/978-3-540-92182-0_59
- ISSN
- 0302-9743
- Article Type
- Article
- Citation
- LECTURE NOTES ON COMPUTER SCIENCE, vol. LNCS 5369, page. 668 - 679, 2008-12
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.