By the classical visibility definition in computational geometry, two points are visible from each other if only the two points can be connected by a line segment without any disturbance. In the real world, however, the visibility is determined by more complicate conditions and the word "visible" has different meaning according to the application where the visibility is used. In order to represent such characteristics, fuzzy visibility defined based on the fuzzy set theory is proposed in this thesis.
According to the condition by which the visibility degree is determined, two kinds of fuzzy visibilities are considered in this thesis. One is Type I fuzzy visibility which is defined on the common sense that the closer object is visible better. The other is Type II fuzzy visibility in which the visibility degree is determined by the number of guards from which an object is visible simultaneously.
The relation between the distance and the degree of visibility is considered in Type I fuzzy visibility. Using a Type I fuzzy visibility, fuzzy polygons such as fuzzy kernel and fuzzy visibility polygons are introduced and their shapes and properties are discussed. All points in a fuzzy polygon have membership values which is defined by an Type I fuzzy visibility function and represent their degrees of membership for the kernel or the visibility polygons.
By an α-cut of the Type I fuzzy visibility, α-visibility is defined. Two points are said to be α-visible if they are visible to the degree of α. Using the α-visibility, two visibility problems are defined and solved. First, the linear algorithms are presented to compute the α-visibility polygons. And a cubic algorithm is developed for computing a rectilinear path problem when the path must be constructed with the minimum number of edges and all adjacent vertices in the path must be α-visible.
The relation between the number of guards and the degree of visibility is considered in Type II fuzzy visibility. Using the Type II fuzzy visibility, the m-visibility is defined. A point is said to be m-visible from at least m distinct points. For some shapes of art gallery, the minimum number of guards for m-visibility are characterized. For a simple polygon and a rectilinear polygon, art gallery theorem and rectilinear art gallery theorem are simply extended to the m-visibility cases by multiflying m. But for a point star-shaped polygon which is visible from only one point, it is proved that only 2(m-1)+1 or 3(m-1)+1 guards are necessary according to its condition.
Using Type II fuzzy visibility, a polygon decomposition problem is also introduced. In the decomposition, all points in each subpolygon must have the same visibility degree. For a 1-spiral polygon, a square algorithm to compute the decomposition is presented.
Generally, most visibility problems using the fuzzy visibility have larger complexities than the classical visibility ones. Using the fuzzy visibility defined in this thesis, however, we will be able to make more realistic geometrical models. This thesis has shown such visibility problems having efficient solutions.
그래픽스, 패턴인식, 로봇제어 등 가시성이 관련된 응용분야는 매우 많다. 계산기하학에서 주로 사용되어온 가시성의 정의에 의하면, 임의의 두 점이 장애물 없이 연결될 수만 있으면 서로 가시하다. 그러나 "가시하다"라는 의미는 사용된 상황에 따라 다르게 해석되는 경우가 많으며, 또한 얼마나 잘 보이는가는 복잡한 여러개의 조건들에 의해 결정된다. 이러한 특성을 반영하기 위하여 본 논문에서는 퍼지 집합을 사용하여 가시성을 정의하였다.
가시정도를 결정하는 조건에 따라 두 종류의 퍼지 가시성을 정의했다. 첫째로, Type Ⅰ 퍼지 가시성은 관찰자와 물체 사이의 거리에 따라 가시정도를 결정하며, 그 관계가 Type Ⅰ 퍼지 가시함수에 의해 표현된다. 즉 Type Ⅰ 퍼지 가시성은 가까운 물체일수록 더 잘 보인다는 일반적인 사실을 퍼지집합을 사용하여 나타낸 것이다.
Type Ⅰ 퍼지 가시성을 사용하여 퍼지 커널, 퍼지 가시다각형 등과 같은 퍼지 다각형을 정의할 수 있다. 이때 다각형내의 모든 점에 대해 그 점이 커널, 혹은 가시다각형에 속하는 정도를 표시하는 소속정도가 Type Ⅰ 퍼지 가시함수를 사용하여 정의된다.
α-가시성은 Type Ⅰ 퍼지 가시성의 α-절단으로 정의되는 가시성 개념으로, 두 점이 α 이상의 가시정도로 보이면 α-가시하다고 한다. 본 논문에서는 α-가시성을 이용하여 다각형의 커널과 가시다각형을 구하는 문제들을 다루었다. 특히 주어진 경비원의 형태가 점, 선분, 블록체인 혹은 블록다각형일때 그 경비원으로부터 완전히 보이는 가시영역을 구하는 문제에 대해 선형시간 알고리즘이 가능함을 보였다.
클립경로문제는 α-가시성을 이용하여 본 논문에서 제안된 최단경로 문제이다. 주어진 직교다각형 내의 두 점을 연결하는 직교클립경로는 수평, 수직 선분으로만 구성되고, 인접하는 모든 정점간에 α-가시성이 만족되는 경로로, 구성하는 클립(혹은 정점)의 개수를 최소화하는 직교클립경로를 구하는 $O(n^3)$ 알고리즘을 제시하였다.
둘째로 Type Ⅱ 퍼지 가시성은 한 물체를 동시에 볼 수 있는 경비원의 수가 많을수록 그 물체를 잘 지킬 수 있다는 사실을 반영한다. 즉 경비원의 수가 많을수록 Type Ⅱ 퍼지 가시함수에 의해 결정되는 가시정도는 커진다. 또한 임의의 점이 적어도 m개의 점들로부터 보일때 그 점은 m-가시하다고 정의한다.
본 논문에서는 m-가시성을 이용하여 화랑문제를 확장정의하고, 몇가지 형태의 화랑을 m-가시하기 위한 최소경비원 수의 성질을 분석하였다. n개의 정점으로 이루어진 단순 다각형 형태의 화랑 전체가 1-가시하기 위해서는 $\lfloor\frac{n}{3}\rfloor$명의 경비원이 때론 필요하고 항상 이 수면 충분하다는 것이 화랑정리이다. 직교다각형의 경우에는 이 값이 $\lfloor\frac{n}{4}\rfloor$이 된다. 본 논문에서는 우선 m-가시해야 하는 경우, 이 값들이 각각 원래의 값에 m을 곱한 값들이 됨을 보였다. 그러나 주어진 화랑의 형태가 오직 한점으로부터만 화랑 전체가 보이는 점·별형다각형인 경우, 그 화랑을 m-가시하기 위해 필요한 최소 경비원 수는 2(m-1)+1명이거나 3(m-1)+1명임을 증명하였다. 또한 충분한 수의 경비원이 주어졌을때 그 수의 경비원을 배치하는 최적알고리즘 역시 제시하였다.
임의의 다각형과 그 다각형내의 배치된 경비원 집합이 주어졌을때, 그 다각형을 Type II 퍼지 가시성을 이용하여 분할하는 문제를 생각해 볼 수 있다. 이때 분할된 각 부분다각형내의 모든 점들이 주어진 경비원 집합으로부터 보이는 정도, 즉 주어진 Type II 퍼지 가시함수에 의해 결정되는 가시정도의 값은 같다. 본 논문에서는 주어진 다각형이 오직 한개씩의 볼록체인과 오목체인으로 구성된 1-나선다각형인 경우, 그 다각형을 분할하는 $O(n^2)$ 알고리즘을 제시하였다.
일반적으로 퍼지가시성을 이용하여 정의된 가시성 문제들의 복잡도는 고전적인 가시성 개념을 이용한 경우보다 커진다. 그러나 퍼지 가시성은 여러 응용분야에서 실제상황에 근접한 기하학적 모델의 구성을 가능하게 한다. 본 논문에서는 두가지 형태의 퍼지가시성을 정의하고, 그 개념을 이용하여 효과적인 해를 얻을 수 있는 가시문제의 몇가지 예를 보였다.
