Efficient generation of k-directional assembly sequences
Let S be a collection of n rigid bodies in 3-space, and let D be a set of k directions in 3-space, where k is a small constant. A k-directional assembly sequence for S, with respect to D, is a linear ordering (s1,⋯, sn) of the bodies in S, such that each Si can be moved to infinity by translating it in one of the directions of D and without intersecting any Sj, for j > i. We present an algorithm that computes a k-directional assembly sequence, or decides that no such sequence exists, for a set of polyhedra. The algorithm runs in O(km4/3+ϵ) time, where m is the total number of vertices of the polyhedra. We also give an algorithm for 'k-directional' rotational motions.
Agarwal, PK; De Berg, M; Halperin, D; Sharir, M
Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms
Volume / Issue
Start / End Page
International Standard Book Number 10 (ISBN-10)