On the complexity of assembly partitioning

DOI10.1016/0020-0190(93)90085-NMaRDI QIDQ1313730zbMATH OpenOpenAlexFDO

Authors Jean-Claude Latombe, Randall H. Wilson, Lydia E. Kavraki

Publication date 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90085-n

zbMATH Keywords

computational complexitycomputational geometrymotion planningassembly planningassembly partioning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the complexity of some partition problems
• Publication:4728240
• A note on the complexity of a partition algorithm
• Computing and Combinatorics
• The complexity of vector partition
• Complexity of graph partition problems
• The parallel complexity of coarsest set partition problems
• Partitioning of processor arrays: a piecewise regular approach
• Partitioning processor arrays under resource constraints

Cites work

• scientific article; zbMATH DE number 3945379 (Why is no real title available?)
• scientific article; zbMATH DE number 3784967 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• DISASSEMBLING TWO-DIMENSIONAL COMPOSITE PARTS VIA TRANSLATIONS
• Objects that cannot be taken apart with two hands
• On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
• Separating two simple polygons by a sequence of translations

Cited in

(10)

• On the complexity of one-shot translational separability.
• Intractability of assembly sequencing: unit disks in the plane
• scientific article; zbMATH DE number 4155942 (Why is no real title available?)
• Symmetric assembly puzzles are hard, beyond a few pieces
• Polyhedral assembly partitioning with infinite translations or the importance of being exact
• scientific article; zbMATH DE number 797431 (Why is no real title available?)
• Minimal fixturing of frictionless assemblies: Complexity and algorithms
• Polyhedral Assembly Partitioning Using Maximally Covered Cells in Arrangements of Convex Polytopes
• Symmetric assembly puzzles are hard, beyond a few pieces
• Partitioning a planar assembly into two connected parts is NP-complete

This page was built for publication: On the complexity of assembly partitioning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1313730)