Efficient generation of k-directional assembly sequences


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