두 가시성 다각형의 교집합과 합집합을 구하는 효율적인 RMESH 알고리즘 (Efficient RMESH Algorithms for Computing the Intersection and the Union of Two Visibility Polygons)

서지정보

· 발행기관 : 한국정보통신학회
· 수록지 정보 : 한국정보통신학회논문지 / 20권 / 2호 / 401 ~ 407페이지
· 저자명 : 김수환

초록

단순 다각형 내부의 두 점 와 가 주어질 때 다음의 문제를 고려할 수 있다. (1) 다각형에서 와 둘 다로부터 가시적인 점들의 집합을 구하라. (2) 와 둘 중의 적어도 하나로부터 가시적인 점들의 집합을 구하라. 이 문제들은 두 가시성 다각형 사이의 교집합과 합집합을 구하는 문제에 해당한다. 본 논문에서는 재구성가능한 메쉬(RMESH)에서 이 문제들을 해결하는 알고리즘을 고려한다. 일반적인 두 다각형의 교차 영역을 구하는 알고리즘[1]을 이용하면, 두 가시성 다각형의 교집합을 구하는 문제를 크기의 RMESH에서 상수 시간에 해결할 수 있다. 여기서 은 두 가시성 다각형의 꼭짓점 개수의 합이다. 본 논문에서는 가시성 다각형의 특성을 이용하여 평면 분할 그래프를 크기의 RMESH에서 상수 시간에 구축하고, 이를 통해 두 가시성 다각형의 교집합뿐만 아니라 합집합도 시간에 구하는 알고리즘을 제시한다. 이 알고리즘은 기존의 결과에 비해 병렬 알고리즘의 비용을 나타내는 프로세서-시간 곱 지표를 에서 으로 개선한다.

영어초록

We can consider the following problems for two given points and in a simple polygon . (1) Compute the set of points of which are visible from both and . (2) Compute the set of points of which are visible from either or . They are corresponding to the problems which are to compute the intersection and the union of two visibility polygons. In this paper, we consider algorithms for solving these problems on a reconfigurable mesh(in short, RMESH). The algorithm in [1] can compute the intersection of two general polygons in constant time on an RMESH with size , where is the total number of vertices of two polygons. In this paper, we construct the planar subdivision graph in constant time on an RMESH with size using the properties of the visibility polygon for preprocessing. Then we present time algorithms for computing the union as well as the intersection of two visibility polygons, which improve the processor-time product from to .

참고자료

· 없음