Xue-Hou TAN Tomio HIRATA Yasuyoshi INAGAKI
Recently much attention has been devoted to the problem of translating a set of geometrical objects in a given direction, one at a time, without allowing collisions between the objects. This paper studies the translation problem in three dimensions on a set of c-oriented faces", that is, the faces whose bounding edges have a constant number c of orientations. We solve the problem in O(N log2 NK) time and O(N log N) space, where N is the total number of edges of the faces and K is the number of edge intersections in the projection plane. As an intermediate step, we also solve a problem related to ray-shooting. The algorithm for translating c-oriented faces finds uses in computer graphic systems.