In this thesis, we investigate the notion of weak visibility in a simple polygon, and consider three classes of visibility problems concerning the edge visibility, the diagonal visibility, and the monotone-visibility, respectively.
First, we propose a class of polygons called weakly star-shaped concerning the edge visibility. A polyon P is weakly star-shaped if there exists a point in P which is weakly visible from all edges and its weak-kernel is the maximal set of such points. It needs $Ω(n^2)$ time to explicitly compute all edge visibility polygons in order to obtain the weak-kernel of a polygon. However, we present an O(n log n) time algorithm for computing the weak-kernel of a polygon by exploiting the weak visibility of a simple polygon.
Second, we consider the diagonal visibility in a polygon. A guard diagonal is an edge or an internal diagonal from which a polygon is weakly visible. A polygon has a guard diagonal is said to be diagonal-visible. We consider the following three problems concerning the diagonal visibility in a polygon. First, determining whether or not a given polygon is diagonal-visible.
Second, compute all guard diagonals of a polygon. Third, given a query diagonal, determine whether or not it is a guard diagonal. For these problems, we first construct a data structure for keeping all guard diagonals in O(n log n) time and O(n) space. Then, using this data structure, we show that these problems can be solved in O(n log n), O(n log n k), O(1) time, respectively, where k is the number of guard diagonals.
Finally, we introduce a new notion of visibility called monotone-visibility. Two points inside a polygon are said to be monotone-visible from each other if there exists an internal path connecting them which is monotone with respect to both x-axis and y-axis. The point monotone-visibility polygon from a point z inside a polygon P is the set of points of P which are monotone-visible from z. The edge monotone-visibility polygon from an edge e of P is the set of points of Pwhich are weakly monotone-visible from e. We present linear time algorithms for computing a point monotone-visibility polygon and an edge monotone-visibility polygon. We also show that the monotone-visibility can be of used to efficiently solve some problems in linear time that previously required local-triangulation.
본 논문에서는 다각형에서의 약가시성(weak visibility)에 관련된 기존의 연구 결과와 응용에 대해서 조사하고, 에지 가시성(edge visibility), 대각 가시성(diagonal visibility), 단조 가시성(monotone-visibility)에 관련된 세가지 부류의 문제를 제시하고 해결한다.
먼저, 다각형의 에지 가시성을 이용한 다각형의 부류인 약가시 다각형(weak starshaped polygon)을 제시한다. 약가시 다각형은 모든 에지로 부터 보이는 내부의 점을 가지고 있는 다각형이고, 약가시 커널(weak-kernel)은 그러한 점들의 최대 집합이다. 약가시 커널을 구하기 위해 모든 에지 가시성 다각형을 구하는 것은 $Ω(n^2)$ 시간이 필요하다. 그러나, 약가시 다각형의 특성을 이용하여, O(n log n) 시간에 약가시 커널을 구하는 알고리즘을 제시한다.
다음으로, 다각형의 대각 가시성에 관련된 문제를 고려한다. 다각형의 경비 대각선은 다각형의 내부를 전부 볼 수 있는 에지 또는 내부 대각선을 말한다. 대각 가시 다각형은 경비대각선을 가진 다각형이다. 본 논문에서는 다음의 세가지 문제를 다루었다. 첫째, 주어진 다각형이 대각 가시 다각형인지를 판별하라. 둘째, 다각형의 모든 경비 대각선을 구하라. 세째, 주어진 질의 대각선이 경비 대각선인지를 판별하라. 이 문제들을 해결하기 위해, 먼저, 모든 경비 대각선에 대한 정보를 저장하는 자료 구조를 O(n log n) 시간과 O(n) 공간에 구한다. 그리고, 이 자료 구조를 이용하여, 세 문제가 각각 O(n log n), O(n log n+k), O(1) 시간에 해결될 수 있음을 보인다, 여기서 k는 경비 대각선의 총 개수 이다.
마지막으로, 새로운 가시 개념인 단조 가시성을 제시한다. 다각형 내부의 두 점을 연결하는, 좌표축에 단조적인 내부 경로가 존재하면, 그 두 점은 서로 단조 가시적이라고 말한다. 다각형 P의 한 점 z로 부터의 점 단조 가시성 다각형은 z로 부터 단조 가시적인 P의 모든 점들의 집합이고, P의 한 에지 e로 부터의 에지 단조 가시성 다각형은 e로 부터 약 단조 가시적인 P의 모든 점들의 집합이다. 본 논문에서는 점 단조 가시성 다각형과 에지 단조 가시성 다각형을 구하는 선형 시간의 알고리즘을 제시한다. 또한, 단조 가시성이 삼각 분할을 필요로 하는 여러 문제들을 효율적으로 해결하기 위해 사용될 수 있음을 보인다.
