Covering a simple polygon by monotone directions
SCIE
SCOPUS
- Title
- Covering a simple polygon by monotone directions
- Authors
- Ahn, HK; Brass, P; Knauer, C; Na, HS; Shin, CS
- Date Issued
- 2010-07
- Publisher
- ELSEVIER SCIENCE BV
- 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 is an element of 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(5) log(2)n)-time algorithm for k = 2, and O(n(3k+1) log n)-time algorithm for fixed k >= 3. (C) 2009 Elsevier B.V. All rights reserved.
- Keywords
- Polygon; Monotonicity; Plane sweep; Algorithm; MAINTENANCE
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/26543
- DOI
- 10.1016/J.COMGEO.2009.11.002
- ISSN
- 0925-7721
- Article Type
- Article
- Citation
- COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, vol. 43, no. 5, page. 514 - 523, 2010-07
- 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.