On some polyhedra covering problems

Let P-0, P-1 be two simple polyhedra and let P-2 be a convex polyhedron in E-3. Polyhedron P-0 is said to be covered by polyhedra P-1 and P-2 if every point of P-0 is a point of P-1 boolean OR P-2. The following polyhedron co vering problem is studied: given the positions of P-0, P-1, and P-2 in the xy-coordinate system, determine whether or not P-0 can be covered by P-1 bo olean OR P-2 via translation and rotation of P-1 and P-2; furthermore, find the exact covering positions of these polyhedra if such a cover exists. It is shown in this paper that if only translation is allowed, then the cover ing problem of P-0, P-1 and P-2 can be solved in O(m(2)n(2)(m + n)l)) polyn omial time, where m, n, and l are the sizes of P-0, P-1, and P-2, respectiv ely. The method can be easily extended to the problem in E for any fixed d > 3.