Sparse Arrangements and the Number of Views of Polyhedral Scenes
Mark de Berg, Dan Halperin, Mark Overmars, Marc J. van Kreveld · International Journal of Computational Geometry & Applications · 1997
In this paper we study several instances of the problem of determining the maximum number of topologically distinct two-dimensional images that three-dimensional scenes can induce. To bound this number, we investigate arrangements of curves and of surfaces that have a certain sparseness property. Given a collection of n algebraic surface patches of constant maximum degree in 3-space with the property that any vertical line stabs at most k of them, we show that the maximum combinatorial complexity of the entire arrangement that they induce is Θ(n 2 k). We extend this result to collections of hypersurfaces in 4-space and to collections of (d > 1)-simplices in d-space, for any fixed d. We show that this type of arrangements (sparse arrangements) is relevant to the study of the maximum number of topologically different views of a polyhedral terrain. For polyhedral terrains with n edges and vertices, we introduce a lower bound construction inducing Ω(n 5 α(n)) distinct views, and we present an almost matching upper bound. We then analyze the case of perspective views, point to the potential role of sparse arrangements in obtaining a sharp bound for this case, and present a lower bound construction inducing Ω(n 8 α(n)) distinct views. For the number of views of a collection of k convex polyhedra with a total of n faces, we show a bound of O(n 4 k 2 ) for views from infinity and O(n 6 k 3 ) for perspective views. We also present lower bound constructions for such scenes, with Ω(n 4 + n 2 k 4 ) distinct views from infinity and Ω(n 6 + n 3 k 6 ) views when the viewpoint can be anywhere in 3-space.