원문정보
초록
영어
A polygon is (weakly) edge-visible if there exists an edge such that every other point in the polygon is visible from some point in the edge. There are well-known linear-time algorithms [1, 2] for finding all visible edges in a polygon without holes. In a polygon with holes, only a tight bound on the number of visible edges has been established; there may be at most three on the boundary and three on one of the holes [3]. In this paper, we present concrete linear-time algorithms for finding the constant number of visible candidate edges in a polygon with holes. Our algorithms take the similar approach of Shin and Woo [1] in a polygon without holes in order to realize the theoretical results of Park et al. [3] on the number of visible edg-es in a polygon with holes.
목차
1. Introduction
2. Preliminary Definitions
3. Comparing Two Approaches for a Polygon without Holes
4. Determining Visible Candidate Edges in a Holed-Polygon
4.1. Overview of Park et al.’s Results [3]
4.2. Algorithms for a Polygon with Only One Hole
4.3. Algorithms for a Polygon with Multiple Holes
5. Conclusion and Further Researches
5.1. Conclusion
5.2. Further Researches
Acknowledgements
References