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
    CountryChile
    CityValdivia
    Period3/20/063/24/06

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

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

  • Cite this

    Aronov, B., Davis, A. R., Iacono, J., & Yu, A. S. C. (2006). The complexity of diffuse reflections in a simple polygon. In LATIN 2006: Theoretical Informatics - 7th Latin American Symposium, Proceedings (pp. 93-104). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3887 LNCS). https://doi.org/10.1007/11682462_13