On the number of views of translates of a cube and related problems

Boris Aronov, Robert Schiffenbauer, Micha Sharir

    Research output: Contribution to journalArticlepeer-review

    Abstract

    It is known that a general polyhedral scene of complexity n has at most O(n6) combinatorially different orthographic views and at most O(n9) combinatorially different perspective views, and that these bounds are tight in the worst case. In this paper we show that, for the special case of scenes consisting of a collection of n translates of a cube, these bounds improve to O(n4+ε) and O(n6+ε), for any ε>0, respectively. In addition, we present constructions inducing Ω(n4) combinatorially different orthographic views and Ω(n6) combinatorially different perspective views, thus showing that these bounds are nearly tight in the worst case. Finally, we show how to extend the upper and lower bounds to several classes of related scenes.

    Original languageEnglish (US)
    Pages (from-to)179-192
    Number of pages14
    JournalComputational Geometry: Theory and Applications
    Volume27
    Issue number2
    DOIs
    StatePublished - Feb 2004

    Keywords

    • Arrangements
    • Aspect graphs
    • Combinatorial geometry
    • Envelopes
    • Fat objects
    • Orthographic views
    • Perspective views
    • Polyhedral terrains
    • Visibility

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'On the number of views of translates of a cube and related problems'. Together they form a unique fingerprint.

    Cite this