This thesis is concerned with the notion of visibility in two and three dimensional objects. Two kinds of visibility problems are considered: the visibility in isothetic objects and the internal line visibility of a simple polygon.
We introduce the two and three dimensional visible points problems as basic visibility problems for isothetic objects: determine all points in a given point set that are visible from a viewpoint at infinity along one of the coordinate axes with respect to a set of opaque isothetic objects. Optimal algorithms to solve the visible points problems are presented. The algorithms are based on a new data structure called a covering tree.
We illustrate the usefulness of the covering tree and the visible points problems by suggesting three applications involving isothetic objects. First, we present a hidden-line elimination algorithm for isothetic polyhedra which improves the previously best known algorithm for the same problem. Second, we describe an optimal query time algorithm for the three dimensional visibility searching problem. Finally, we show that whether or not two non-intersecting isothetic polyhedra with n vertices are separable by a single isothetic translation can be determined in O (nlogn) time and O(n) space.
We consider the problem of internal line visibility of a simple polygon P with n vertices: determine whether or not there exists a line segment inside P from which every point inside P is visible. An O(nlogn) time and O(n) space algorithm for this problem is presented. Also we present a linear time algorithm for triangulating an internally line visible polygon.
평면 또는 공간 상의 물체들에 대한 기하학적인 문제를 해결하기 위한 알고리즘의 효율성에 큰 영향을 미치는 성질 중의 하나로서 가시성(visibility)이 있으며 이에 대해 많은 연구가 되고있다.
본 논문에서는 크게 두 가지 유형의 가시성 문제를 고려하였다. 첫째, 평면 또는 공간상의 직교물체에 대한 새로운 가시성 문제를 정의하였으며 이 문제에 대한 최적 알고리즘을 제시하였다. 또한 이를 이용하면 비가시선 제거 문제(hidden-line elimination problem), 가시성 탐색 문제, 삼차원 직교물체의 분리 가능성 문제를 해결할 수 있음을 보였다. 둘째, 다각형의 점(point) 또는 변(edge)으로부터의 가시성 개념보다 더 일반적인 다각형의 내부 선분으로부터의 가시성을 정의함으로써 가시성에 대한 다각형의 부류를 확장하였으며, 주어진 다각형이 이러한 부류에 속하는지의 여부를 결정하는 알고리즘을 제시하였다. 그리고 이러한 부류에 속하는 다각형의 삼각분할(triangulation)이 쉽게 해결될 수 있음을 보였다.
