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

• 영문명: An disassembling algorithm for two-dimensional composite parts in parallel
• 발행기관: 호서대학교 중앙도서관
• 저자명: 신현철 민용식
• 간행물 정보: 『호서대학교 논문집』제3권, 147~157쪽, 전체 11쪽
• 주제분류: 사회과학 > 무역학
• 파일형태: PDF
• 발행일자: 1995.12.30

국문 초록

본 연구는 병렬컴퓨터상에서 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.

목차

요약

ABSTARCT

Ⅰ. 서론

Ⅱ. 2차원 도형 집합의 분리 알고리즘

참고문헌