DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Chwa, Kyung-Yong | - |
dc.contributor.advisor | 좌경룡 | - |
dc.contributor.author | Kim, Sung-Ho | - |
dc.contributor.author | 김승호 | - |
dc.date.accessioned | 2011-12-13T05:22:49Z | - |
dc.date.available | 2011-12-13T05:22:49Z | - |
dc.date.issued | 1994 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=69070&flag=dissertation | - |
dc.identifier.uri | http://hdl.handle.net/10203/32998 | - |
dc.description | 학위논문(박사) - 한국과학기술원 : 전산학과, 1994.2, [ v, 92 p. ] | - |
dc.description.abstract | This thesis is concerned with the notion of d-visibility in a simple polygon. Two points in a simple polygon P are said to be d-visible if the line segment l joining them is contained in P and the length of l is d or less. In applications such as computer graphics and robot vision, the notion of d-visibility is more suitable than the commonly used definition of visibility which is equivalent to d-visibility with infinite d. First, we consider the problem concerning the point d-visibility. The d-kernel of P, denoted by d-K(P), is the set of all points in P such that every point in P is d-visible from any point in d-K(P). We present an algorithm for finding d-K(P), if any. We also present an algorithm for computing the minimum distance d, if any, such that d-K(P) is not empty. We show that these algorithms can be run in O(n) time, where n is the number of vertices. Second, we consider the problem concerning the edge d-visibility. We develop an algorithm for finding the edge d-visibility polygon from an edge e in P and an algorithm for computing the minimum $d_e$ for an edge e in P such that P is edge $d_e$-visible from e. Both algorithms run in time linear in the number of vertices in P. Third, we consider the externally d-visibility problems. Two points are said to be externally d-visible each other if the line segment l joining them does not intersect the interior of a polygon and the length of l is d or less. We present an algorithm for computing externally d-visible boundary edges of a set of nonoverlapping simple polygons from a point in the exterior of the polygons. It runs in O(n + clog m) time, where n is the total number of vertices, m is the number of polygons and c is the number of maximal sequences of connected edges. | eng |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.title | Visibility algortihms under distance constraint | - |
dc.title.alternative | 거리 제약을 가지는 가시성 알고리즘 | - |
dc.type | Thesis(Ph.D) | - |
dc.identifier.CNRN | 69070/325007 | - |
dc.description.department | 한국과학기술원 : 전산학과, | - |
dc.identifier.uid | 000815043 | - |
dc.contributor.localauthor | Chwa, Kyung-Yong | - |
dc.contributor.localauthor | 좌경룡 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.