# 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