2017년 추계학술대회
Current Result Document :
| 한글제목(Korean Title) |
좌표축에 평행한 직사각형들의 합집합을 구하는 상수시간 RMESH 알고리즘 |
| 영문제목(English Title) |
A Constant Time RMESH Algorithm for the Union of Iso-Oriented Rectangles |
| 저자(Author) |
김수환
최진오
Soo-Hwan Kim
Jinoh Choi
|
| 원문수록처(Citation) |
VOL 21 NO. 02 PP. 0627 ~ 0629 (2017. 10) |
한글내용
(Korean Abstract) |
평면 상에 주어진 개의 직사각형에 대한 합집합과 교집합을 구하는 문제에 대해 많은 연구 결과가 나와 있다. Lipski와 Preparata(1981)는 좌표축에 평행한 직사각형의 합집합을 구하는 문제에 대해서 O(nlogn) 시간과 O(nlogn) 공간의 순차 알고리즘을 제시하였고[1], Alevizos(2013)는 이를 개선한 O(nlogn) 시간과 O(n) 공간의 개선된 순차 알고리즘을 제시하였다[2]. 본 논문에서는 좌표축에 평행한 직사각형들의 교집합이 공집합이 아닌 경우에 대한 직사각형들의 합집합을 구하는 문제를 고려한다. 이 경우, 직사각형들의 합집합은 하나의 연결된 영역, 즉 직교다각형이 된다. 본 논문에서는 재구성가능한 메쉬(RMESH) 모델에서 상수 시간에 이 문제를 해결하는 병렬 알고리즘을 제시한다.
|
영문내용
(English Abstract) |
There are a lot of research results on the problem of finding the union and intersection of n rectangles on a plane. Lipski와 Preparata(1981) presented a sequential algorithm with O(nlogn) time and O(nlogn) space for the problem of finding the union of rectangles whose sides are parallel to the coordinate axes[1]. Alevizos(2013) presented an improved O(nlogn) time and O(n) space algorithm for the same problem[2]. In this paper, we consider the problem of finding the union of iso-oriented rectangles such that the intersection of them is not an empty set. In this case, the union of the rectangles becomes a connected area, that is, an orthogonal polygon. In this paper, we propose a parallel algorithm that solves this problem in constant time in a reconfigurable mesh(in short, RMESH) model.
|
| 키워드(Keyword) |
Reconfigurable mesh
Parallel algorithm
Iso-oriented Rectangles
Union
|
| 파일첨부 |
PDF 다운로드
|
