Sparse arrangements and the number of views of polyhedral scenes

M. Berg, de, D. Halperin, M.H. Overmars, M.J. Kreveld, van

    Research output: Contribution to journalArticleAcademicpeer-review

    19 Citations (Scopus)

    Abstract

    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 T(n2 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 O(n5 a(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 O(n8a(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(n4 k2) for views from infinity and O(n6 k3) for perspective views. We also present lower bound constructions for such scenes, with O(n4 + n2 k4) distinct views from infinity and O(n6 + n3 k6) views when the viewpoint can be anywhere in 3-space.
    Original languageEnglish
    Pages (from-to)175-195
    JournalInternational Journal of Computational Geometry and Applications
    Volume7
    Issue number3
    DOIs
    Publication statusPublished - 1997

    Fingerprint

    Dive into the research topics of 'Sparse arrangements and the number of views of polyhedral scenes'. Together they form a unique fingerprint.

    Cite this