On The Computational Complexity Of Hierarchical Radiosity
switch to german Deutsche Version

Robert Garmann, Heinrich Müller:
On The Computational Complexity Of Hierarchical Radiosity,
in: Computer Science in Perspective - Essays Dedicated to Thomas Ottmann, R. Klein, H.-W. Six, L. Wegner (eds.), LNCS 2598, Springer-Verlag, Berlin, 2003, 167-178

Abstract: The hierarchical radiosity algorithm is an efficient approach to simulation of light with the goal of photo-realistic image rendering. Hanrahan et. al. describe the initialization and the refinement of links between the scene's patches based upon a user-specified error parameter Fe. They state that the number of links is linear in the number of elements if Fe is assumed to be a constant. We present a result based upon the assumption that the geometry is constant and Fe approaches 0 in a multigridding-procedure. Then the algorithm generates L = Theta(N2) links where N denotes the number of elements generated by the algorithm.

Text: pdf (347K)
Robert Garmann, June 10, 2007