Efficient generation of k-directional assembly sequences
Published
Conference Paper
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.
Duke Authors
Cited Authors
- Agarwal, PK; De Berg, M; Halperin, D; Sharir, M
Published Date
- January 28, 1996
Published In
- Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms
Volume / Issue
- Part F129447 /
Start / End Page
- 122 - 131
International Standard Book Number 10 (ISBN-10)
- 0898713668
Citation Source
- Scopus