Translating a convex polyhedron over monotone polyhedra

摘要

Let S be a collection of geometric objects in R~3, and let P be another geometric object in R~3. The free configuration space of P with respect to S is the set of all possible placements of P so that P does not intersect the set S. Finding combinatorial and computational bounds for the computation of the free configuration space is a currently active area of research in computational geometry. We show in this paper that the free configuration space of a convex polyhedron P freely translating over a polyhedral terrain having a convex projection T can be computed in O(nm + k + t) time in the worst case, where m and n are the number of faces of P and T, respectively, k denotes the size of the output and t is a parameter whose value could be, at most, O(n~2m log n).