Visibility with One Reflection

B. Aronov, A. R. Davis, T. K. Dey, S. P. Pal, D. C. Prasad

    Research output: Contribution to journalArticle

    Abstract

    We extend the concept of the polygon visible from a source point S in a simple polygon by considering visibility with two types of reflection, specular and diffuse. In specular reflection a light ray reflects from an edge of the polygon according to the rule: the angle of incidence equals the angle of reflection. In diffuse reflection a light ray reflects from an edge of the polygon in all inward directions. Several geometric and combinatorial properties of visibility polygons under these two types of reflection are described, when at most one reflection is permitted. We show that the visibility polygon Vs(S) under specular reflection may be nonsimple, while the visibility polygon Vd(S) under diffuse reflection is always simple. We present a Θ(n2) worst-case bound on the combinatorial complexity of both Vs(S) and Vd(S) and describe simple O(n2 log2 n) time algorithms for constructing the sets.

    Original languageEnglish (US)
    Pages (from-to)553-574
    Number of pages22
    JournalDiscrete and Computational Geometry
    Volume19
    Issue number4
    DOIs
    StatePublished - Jun 1998

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics

    Fingerprint Dive into the research topics of 'Visibility with One Reflection'. Together they form a unique fingerprint.

  • Cite this

    Aronov, B., Davis, A. R., Dey, T. K., Pal, S. P., & Prasad, D. C. (1998). Visibility with One Reflection. Discrete and Computational Geometry, 19(4), 553-574. https://doi.org/10.1007/PL00009368