ABSTRACT
This paper studies motion planning of polyhedra in contact, which has a crucial role to automate mechan ical assembly processes. We have been attacking this problem based on an algebraic formulation. We first re visit our complete and implemented algorithm for mo tion planning of convex polyhedra in contact to see that the complexity of the algebraic part heavily depends how the geometric problem is reduced to it. Then we present a predicate for nonconvex polyhedra in contact without overlapping, give algorithms to be applied to the non convex case, and investigate their geometric and alge braic complexity.