Time Complexity of Monte Carlo Radiosity

Abstract

The time complexity of Monte Carlo radiosity is discussed, and a proof is given that the expected number of rays required to produce a satisfactory radiosity solution for N zones is O(N). A satisfactory solution is defined to be one in which the variance of radiance estimates for each zone is below a predefined threshold. The proof assumes that the radiance is bounded, and the area ratio of the largest to smallest zone is bounded.