병렬 컴퓨터상에서 2차원상의 composite 분리 알고리즘

An disassembling algorithm for two-dimensional composite parts in parallel

본 연구는 병렬컴퓨터상에서 2차원상에서의 단순 다각형을 포함하는 조합부의 충돌이 없는 translations을 통한 분리의 computational complexity에 관하여 기술하였다. 본 연구의 첫번 결과로는 Nurmi와 Toussaint에 의하여 제안된 문제에 대한 해결책으로서 조합부의 분리를 위하여 동일 방향에 대하여 실행된 순차적인 translation의 연산이 O (1/p(Mn+M log M))의 complexity를 갖는 알고리즘을 보여준다. 두번째 결과로는 조합부가 분리되어질 수 있는지 또는 구성부 상호간에 접합이 있는지를 파악하는 문제를 Ω (1/p(Mn+M log M))의 복잡도내에 해결할 수 있음을 보여준다.

This paper presents lower bounds and matching upper bounds for 2-dim. disassemblies via translations in a common direction in parallel machine. Since this paper is the elimination of Nurmi and Toussaint s problem, the first result of this paper is an O(1/p(Mn+M log M) algorithm for computing a sequence of transalations using parallel machine. The second result is an Ω(1/p(Mn+M log M)) lower bound of detecting whether a composite part can be disassembled or contains interlocking subparts.