The complexity of diffuse reflections in a simple polygon

Boris Aronov, Alan R. Davis, John Iacono, Albert Siu Cheong Yu

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

    Abstract

    The complexity of the visibility region formed by a point light source after k diffuse reflections in a simple n-sided polygon is O(n°), which is the first result polynomial in n, with no dependence on k. This bound is an exponential improvement over the previous bound of O(n2[(k+1)/2]+1) due to Prasad et al. [8].

    Original languageEnglish (US)
    Title of host publicationLATIN 2006
    Subtitle of host publicationTheoretical Informatics - 7th Latin American Symposium, Proceedings
    Pages93-104
    Number of pages12
    DOIs
    StatePublished - 2006
    EventLATIN 2006: Theoretical Informatics - 7th Latin American Symposium - Valdivia, Chile
    Duration: Mar 20 2006Mar 24 2006

    Publication series

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

    Other

    OtherLATIN 2006: Theoretical Informatics - 7th Latin American Symposium
    Country/TerritoryChile
    CityValdivia
    Period3/20/063/24/06

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science

    Fingerprint

    Dive into the research topics of 'The complexity of diffuse reflections in a simple polygon'. Together they form a unique fingerprint.

    Cite this