On Some Polyhedra Covering Problems

Abstract

Let P ⁰, P ¹ be two simple polyhedra and let P ² be a convex polyhedron in E ³. Polyhedron P ⁰ is said to be covered by polyhedra P ¹ and P ² if every point of P ⁰ is a point of P ¹ ∪ P ². The following polyhedron covering problem is studied: given the positions of P ⁰, P ¹, and P ² in the xy-coordinate system, determine whether or not P ⁰ can be covered by P ¹ ∪ P ² via translation and rotation of P ¹ and P ²; 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 covering problem of P ⁰, P ¹ and P ² can be solved in O(m ² n ²(m + n)l)) polynomial time, where m, n, and l are the sizes of P ⁰, P ¹, and P ², respectively. The method can be easily extended to the problem in E ^d for any fixed d > 3.