ON THE COMPLEXITY OF ASSEMBLY PARTITIONING

被引：35

作者：

KAVRAKI, L

LATOMBE, JC

WILSON, RH

机构：

[1] Robotics Laboratory, Department of Computer Science, Stanford University, Stanford, CA 94305

来源：

INFORMATION PROCESSING LETTERS | 1993年 / 48卷 / 05期

基金：

美国国家科学基金会;

关键词：

COMPUTATIONAL COMPLEXITY; COMPUTATIONAL GEOMETRY; ASSEMBLY PLANNING; MOTION PLANNING;

D O I：

10.1016/0020-0190(93)90085-N

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper studies the complexity of the assembly partitioning problem in the plane: given a collection of non-overlapping polygons, decide if there is a proper subcollection of them that can be removed as a rigid body without colliding with or disturbing the other parts of the assembly. It is shown that assembly partitioning is NP-complete. The result extends to several interesting variants of the problem.

引用

页码：229 / 235

页数：7

共 14 条

[1]

ARKIN E, 1989, 5TH P ANN ACM S COMP, P334

[2]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[3]

Guibas L. J., 1983, ADV COMPUTING RES

[4]

HALBERSTAM H., 1983, SEQUENCES

[5]

Homem de Mello L.S., 1991, COMPUTER AIDED MECHA

[6]

KAVRAKI L, 1993, STANCS931467 STANF U

[7]

NATARAJAN BK, 1988, 4TH P ANN S COMP GEO, P299

[8] DISASSEMBLING TWO-DIMENSIONAL COMPOSITE PARTS VIA TRANSLATIONS [J].

Nussbaum, Doron ;

Sack, Joerg-Ruediger .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1993, 3 (01) :71-84

[9] SEPARATING 2 SIMPLE POLYGONS BY A SEQUENCE OF TRANSLATIONS [J].

POLLACK, R ;

SHARIR, M ;

SIFRONY, S .

DISCRETE & COMPUTATIONAL GEOMETRY, 1988, 3 (02) :123-136

[10] ON THE PIANO MOVERS PROBLEM .1. THE CASE OF A TWO-DIMENSIONAL RIGID POLYGONAL BODY MOVING AMIDST POLYGONAL BARRIERS [J].

SCHWARTZ, JT ;

SHARIR, M .

COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS, 1983, 36 (03) :345-398

← 1 2 →