On the number of views of polyhedral scenes

• Version published in LNCS 2098.  

Abstract: It is known that a scene consisting of k convex polyhedra of total complexity n has at most O(n^4k^2) distinct orthographic views, and that the number of such views is \Omega((nk^2+n^2)^2) in the worst case. The corresponding bounds for perspective views are O(n^6k^3) and Omega((nk^2+n^2)^3), respectively. In this paper, we close these gaps by improving the lower bounds. We construct an example of a scene with Theta(n^4k^2) orthographic views, and another with Theta(n^6k^3) perspective views. Our construction can also be used to improve the known lower bounds for the number of silhouette views and for the number of distinct views from a viewpoint moving along a straight line.