Efficient ray shooting and hidden surface removal

In this paper we study the ray-shooting problem for three special classes of polyhedral objects in space: axis-parallel polyhedra, curtains (unbounded polygons with three edges, two of which are parallel to thez-axis and extend downward to minus infinity), and fat horizontal triangles (triangles parallel to thexy-plane whose angles are greater than some given constant). For all three problems structures are presented usingO(n 2+O(n1 + e Ök )O(n1+k) , wheren is the total number of vertices of the polyhedra andk is the size of the output. This is the first output-sensitive algorithm for this problem that does not need a depth order on the faces of the polyhedra