ISSN:
1573-2886
Keywords:
computational geometry
;
polyhedra covering
;
NP-hard
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract 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 ∪ P 2. The following polyhedron covering 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 ∪ 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 covering problem of P 0, P 1 and P 2 can be solved in O(m 2 n 2(m + n)l)) polynomial time, where m, n, and l are the sizes of P 0, P 1, and P 2, respectively. The method can be easily extended to the problem in E d for any fixed d 〉 3.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1009833410742
Permalink
