DISASSEMBLING TWO-DIMENSIONAL COMPOSITE PARTS VIA TRANSLATIONS

被引：6

作者：

Nussbaum, Doron ^{[1
]}

Sack, Joerg-Ruediger ^{[2
]}

机构：

[1] Devron Technol, Ottawa, ON K1G 2Y8, Canada

[2] Carleton Univ, Sch Comp Sci, Ottawa, ON K1S 5B6, Canada

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1993年 / 3卷 / 01期

关键词：

Computational geometry; translation motion; upper-bounds; lower-bounds;

D O I：

10.1142/S0218195993000051

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper deals with the computational complexity of disassembling 2-dimensional composite parts (comprised of M simple n-vertex polygons) via collision-free translations. The first result of this paper is an O(Mn + M log M) algorithm for computing a sequence of translations (performed in a common direction) to disassemble composite parts. The algorithm improves on the O(Mn log Mn) bound previously established for this problem and is easily seen to be optimal. The problem had been posed by Nurmi and by Toussaint. The second result of this paper is an Omega(Mn + M log M) lower bound proof for the problem of detecting whether a composite part can be disassembled, or contains interlocking subparts. Thus, detecting the existence of a disassembly sequence is as hard as computing one. As a consequence, the algorithm for computing a disassembly sequence is optimal also for the detecting problem.

引用

页码：71 / 84

页数：14

共 18 条

[1] INTERSECTION OF CONVEX OBJECTS IN 2-DIMENSION AND 3-DIMENSION [J].

CHAZELLE, B ;

DOBKIN, DP .

JOURNAL OF THE ACM, 1987, 34 (01) :1-27

[2]

Chazelle B., 1983, CS8334 U WAT

[3]

Dean J. A., 1985, Proceedings of the Twenty-third Annual Allerton Conference on Communication, Control, and Computing, P496

[4]

DEHNE F, 1981, VISUAL COMPUT, P227

[5]

ELGINDY H, 1983, J ALGORITHMS, V2, P191

[6]

Guibas L. J., 1983, ADV COMPUTING RES

[7] VISIBILITY OF A SIMPLE POLYGON [J].

LEE, DT .

COMPUTER VISION GRAPHICS AND IMAGE PROCESSING, 1983, 22 (02) :207-221

[8]

Natarajan B. K., 1988, Proceedings of the Fourth Annual Symposium on Computational Geometry, P299, DOI 10.1145/73393.73424

[9] ON TRANSLATING A SET OF OBJECTS IN TWO-DIMENSIONAL AND 3-DIMENSIONAL SPACE [J].

NURMI, O .

COMPUTER VISION GRAPHICS AND IMAGE PROCESSING, 1986, 36 (01) :42-52

[10]

NURMI O, 1988, LECTURE NOTES COMPUT, V344, P202

← 1 2 →