ERROR AND COMPLEXITY OF RANDOM-WALK MONTE-CARLO RADIOSITY

In this paper, we study the error and complexity of the discrete rando m walk Monte Carlo,technique for Radiosity, both the shooting and gath ering methods; We show that the shooting method exhibits a lower compl exity than the gathering one, and under some constraints, it has a lin ear complexity. This is an improvement over a previous result that poi nted to an O(n log n) complexity. We give and compare three unbiased e stimators for each method, and obtain closed forms and bounds for thei r variances. We also bound the expected value of the Mean Square Error (MSE). Some of the results obtained are also shown to be valid for th e nondiscrete gathering case. We also give bounds for the variances an d MSE for the infinite path length estimators; these bounds might be u seful in the study of the biased estimators resulting of cutting off t he infinite path.