On the Number of Views of Polyhedral Terrains.
Pankaj K. Agarwal, Micha Sharir · 1993
We show that the number of topologically-different orthographic views of a polyhedral terrain with n edges is O(n 5+" ), and that the number of topologically-different perspective views of such a terrain is O(n 8+" ), for any " ? 0. Both bounds are almost tight in the worst case. The proofs are simple consequences of the recent almost tight bounds of [11] on the complexity of lower envelopes in higher dimensions. 1 Introduction Let \\Sigma be a polyhedral terrain with n edges in 3-space. That is, \\Sigma is the graph of a continuous bivariate piecewise-linear function. An orthographic view of \\Sigma in some direction ! is defined as follows. Take a plane \\Pi at infinity orthogonal to !. For each point q 2 \\Pi, consider the ray ae q emanating from q in direction !, and let q be the first point, if any, along ae q at which it intersects \\Sigma. We can partition \\Pi into a collection of maximal open connected regions, with the property that for each region f , all points in q 2 f...