登入選單
返回Google圖書搜尋
出版MacGill University. School of Computer Science, 1988
URLhttp://books.google.com.hk/books?id=jcdDGwAACAAJ&hl=&source=gbs_api
註釋Abstract: "Given a simple polygon P consisting of n sides and a line L not intersecting P, we say that P is weakly externally visible from L if for every point x on the boundary of P there exists a point y in L such that the interior of the line segment [x, y] does not intersect the interior of P. Clearly a convex polygon is weakly externally visible from every such line L. However, it is not necessarily so visible from a given line segment. It is shown that, given a convex polygon P, the minimal length line segment from which P is weakly externally visible can be found in O(n) time. The algorithm is based on the solution to a fundamental geometric minimization problem that is of independent interest and should find application in several different contexts."