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.
본 논문에서는 단순 다각형에서의 제한된 가시성(d-가시성)에 관한 개념을 연구하였다. 단순 다각형 P 내의 두 점을 연결하는 선분 l 이 P 에 완전히 포함되고 l 의 길이가 d 이하일 때 그 두점은 서로 d-가시적이다라고 한다. 컴퓨터 그래픽스와 로보트 비젼과 같은 응용분야에서는 d-가시성의 개념이 보통 사용하는 가시성(이는 d-가시성 개념에서 무한대의 d를 가지는 경우와 동일하다.)의 정의보다 더욱 적절한 개념이다.
첫째, 점 가시성에 관한 문제를 다루었다. d-K(P)로 표기되는 P 의 d-커널은 P 내의 모든점이 d-K(P) 내의 어떠한 점으로 부터도 d-가시적인 P 내의 점들의 집합이다. 본 논문에서는 d-K(P)가 존재할 때 이를 구하는 알고리즘을 제시하였다. 또한, d-K(P)가 공집합이 되지 않는 한도내에서 최소 거리 d를 구하는 알고리즘도 제시하였다. 이들 알고리즘은 n 이 다각형의 정점의 갯수일 때 O(n) 시간의 복잡도를 가진다.
둘째, 에지 가시성에 관한 문제를 다루었다. 본 논문에서는 P 에서 어떤 에지 e로 부터 에지 d-가시적인 다각형을 구하는 알고리즘을 개발하였다. 또한, P 가 e로 부터 에지 $d_e$-가시적이기 위한 P 의 에지 e 의 최소 $d_e$를 구하는 알고리즘도 개발하였다. n 이 다각형의 정점의 갯수일 때 두 알고리즘 모두 O(n) 시간에 수행된다.
셋째, 외부 d-가시성 문제를 고려하였다. 두 점을 연결하는 선분 l 이 어떤 다각형의 내부와도 교차하지 않고 l의 길이가 d이하일 때 그 두점은 서로 외부 d-가시적이다라고 한다. 본 논문에서는 서로 중첩되지 않는 다각형의 집합이 있을 때 다각형 외부에 있는 어떤 점으로 부터 외부 d-가시적인 다각형의 경계 에지를 구하는 알고리즘을 제시하였다. 이 알고리즘은 m 이 다각형의 갯수, n 이 다각형 전체 정점의 갯수, c가 연결 에지의 최대 순서열의 갯수일 때 O(n + clogm) 시간에 수행된다.
