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." />


On Translating a Set of C-Oriented Faces in Three Dimensions

Xue-Hou TAN  Tomio HIRATA  Yasuyoshi INAGAKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.3   pp.258-264
Publication Date: 1992/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Keyword: 
computational geometry,  translation problems,  c-oriented faces,  ray-shooting,  priority search trees,  

Full Text: PDF(615.6KB)>>
Buy this Article




Summary: 
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.