期刊名称：International Journal of Software Engineering and Its Applications
印刷版ISSN：1738-9984
出版年度：2014
卷号：8
期号：10
页码：25-36
DOI：10.14257/ijseia.2014.8.10.03
出版社：SERSC
摘要：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.
关键词：Computational geometry; Edge visibility; Gallery problem
