Visibility with multiple reflections

Boris Aronov, Alan R. Davis, Tamal K. Dey, Sudebkumar P. Pal, D. Chithra Prasad

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    We show that the region lit by a point fight 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)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(n2k log n) time and O(n2k) space for any k>1.

    Original languageEnglish (US)
    Title of host publicationAlgorithm Theory - SWAT 1996 - 5th Scandinavian Workshop on Algorithm Theory, Proceedings
    EditorsRolf Karlsson, Andrzej Lingas
    PublisherSpringer Verlag
    Number of pages12
    ISBN (Print)3540614222, 9783540614227
    StatePublished - 1996
    Event5th Scandinavian Workshop on Algorithm Theory, SWAT 1996 - Reykjavik, Iceland
    Duration: Jul 3 1996Jul 5 1996

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other5th Scandinavian Workshop on Algorithm Theory, SWAT 1996

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Visibility with multiple reflections'. Together they form a unique fingerprint.

    Cite this