Visibility with multiple reflections

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

    Research output: Contribution to journalArticlepeer-review

    Abstract

    We show that the region lit by a point light source inside a simple n-gon after at most k reflections off the boundary has combinatorial complexity O(n2k), for any k ≥ 1. A lower bound of Ω((n/k - Θ(1))2k) is also established which matches the upper bound for any fixed k. A simple near-optimal algorithm for computing the illuminated region is presented, which runs in O(n2klog n) time and O(n2k) space for k ≥ 1, and in O(n2 log2 n) time and O(n2) space for k = 1.

    Original languageEnglish (US)
    Pages (from-to)61-78
    Number of pages18
    JournalDiscrete and Computational Geometry
    Volume20
    Issue number1
    DOIs
    StatePublished - Jul 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 multiple reflections'. Together they form a unique fingerprint.

    Cite this